Document information
- University
- Politecnico di Milano
- Degree programme
- Computer Engineering
- Subject
- Formal Languages and Compilers
- Classification
- Exercises · Complete set
- Original format
- Text
- Searchable text
← Back
ExercisesComplete set
Esercitazioni Svolte
Study material for Formal Languages and Compilers, shared by the Studwiz community and reviewed by moderators.
Formal Languages and CompilersComplete set
Document information
What's included in this study material
Study material for Formal Languages and Compilers, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Extracted content from the document
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
Page 1
THEORY OF FORMAL LANGUAGES EXERCISE BOOK A SUITE of 100 EXERCISES WITH SOLUTIONS AA.VV. 9th October 2007 Contents 1 Introduction 1 2 Generative Models 3 2.1 Regular Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Context-Free Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Recognitive Machines 31 3.1 Finite State Automaton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.2 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Pushdown Automaton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.2 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Syntax Analysis 49 4.1 Deterministic Methodologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.1.1 Top-Down (Recursive Descent) Method . . . . . . . . . . . . . . . . . . 49 4.1.2 Bottom-Up (Shift-and-Reduce) Method . . . . . . . . . . . . . . . . . . 58 4.1.3 Miscellanea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 4.2 Earley (List-Based) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5 T ransduction Models and Machines 73 5.1 Syntax-Driven Methods . . . . . . . . . .…
Preview
First page of the document.