04 09 2023 E TS

Page 1

FORMAL LANGUAGES AND COMPILERS prof.s Giovanni Agosta, Luca Breveglieri and Angelo Morzen ti Exam of MONDAY 4 SEPTEMBER 2023 – Theory Part WITH SOLUTIONS – FOR TEACHING PURPOSES THE SOLUTIONS ARE WIDEL Y COMMENTED LAST NAME (SURNAME) + FIRST NAME: (capital letters please) MATRICOLA: SIGNATURE: (or PERSON CODE) TEACHER: □ Prof. G. AGOSTA – □ Prof. L. BREVEGLIERI – □ Prof. A. MORZENTI INSTRUCTIONS - READ CAREFULLY: • The exam is in written form and consists of two parts: 1. Theory (80%): syntax and semantics of languages, divided in four sections: – regular expressions and finite automata – free grammars and pushdown automata – syntax analysis and parsing methodologies – language translation and semantic analysis 2. Lab (20%): compiler design by Flex and Bison • To pass the exam, the candidate must succeed in both parts (th eory and lab), in one call or more calls separately, but within one year (12 months ) between the two parts. • For the theory part to be valid, the candidate must achieve a g rade of at least 10 /20 on each of the four sections. • Correctly answering all the questions that are not marked op tional, allows the candi- date to achieve a high grade (although not the full mark). • For the lab part to be valid, the candidate must achieve a grad e of at least 15 /30. • The final grade is the weighted average of the theory part (80 % ) and of the lab part (20 %), and must be ≥ 18/30. • The exam is open book: textbooks and personal notes are permi tted. • Please write in the free space left and if necessary continue on the back side of the sheet; do not attach new sheets and do not replace the existin g ones. • Time: lab part 1 h – theory part 2 h. 1 Regular Expressions and Finite Automata 20% 1. Consider the finite-state nondeterministic automaton A below, over…