18 01 18

Page 1

FORMAL LANGUAGES AND COMPILERS prof.s Luca Breveglieri and Angelo Morzenti Exam of Thu 18 JANUARY 2018 - Part Theory WITH SOLUTIONS - FOR TEACHING PURPOSES HERE THE SOLUTIONS ARE WIDEL Y COMMENTED LAST + FIRST NAME: (capital letters please) MATRICOLA: SIGNATURE: (or PERSON CODE) INSTRUCTIONS - READ CAREFULLY: • The exam is in written form and consists of two parts: 1. Theory (80%): Syntax and Semantics of Languages – 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. • To pass part theory, the candidate must answer the mandatory (not optional) ques- tions; notice that the full grade is achieved by answering th e optional questions. • 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: part lab 60m - part theory 2h.15m 1 Regular Expressions and Finite Automata 20% 1. Consider the regular expression R1 below, over the two-letter alphabet { a, b }: R1 = ( a | ε )+ ( b a | b a b )∗ Consider also the non-deterministic automaton A2 below, over the same two-letter alphabet{ a, b }, with a spontaneous transition, and with final nodes 1 and 3: 1 2 3 4A2 → → → a b a b b ε Answer the following questions (use the spaces / tables on th e next pages): (a) Determine whether expression R1 is ambiguous, and explain your answer. (b) By first using the Berry-Sethi method and then…