Chapter 3 - Lexical and syntactic analysis. A study of language syntax raises many questions. How does a compiler analyze the syntax of a program? How are syntax errors detected? How does a context-free grammar facilitate the development of a syntactic analyzer? These deeper questions about syntax are addressed in Chapter 3. Chapter 3a provide knowledge of chomsky hierarchy. | Programming Languages 2nd edition Tucker and Noonan Chapter 3 Lexical and Syntactic Analysis Syntactic sugar causes cancer of the semicolon. A. Perlis Contents Chomsky Hierarchy Lexical Analysis Syntactic Analysis Chomsky Hierarchy Regular grammar -- least powerful Context-free grammar (BNF) Context-sensitive grammar Unrestricted grammar Regular Grammar Simplest; least powerful Equivalent to: Regular expression Finite-state automaton Right regular grammar: T*, B N A → B A → Example Integer → 0 Integer | 1 Integer | . | 9 Integer | 0 | 1 | . | 9 Regular Grammars Left regular grammar: equivalent Used in construction of tokenizers Less powerful than context-free grammars Not a regular language { aⁿ bⁿ | n ≥ 1 } ., cannot balance: ( ), { }, begin end Context-free Grammars BNF a stylized form of CFG Equivalent to a pushdown automaton For a wide class of unambiguous CFGs, there are table-driven, linear time parsers Context-Sensitive Grammars Production: α → β |α| ≤ |β| α, β (N T)* ie, lefthand side can be composed of strings of terminals and nonterminals Undecidable Properties of CSGs Given a string and grammar G: L(G) L(G) is non-empty Defn: Undecidable means that you cannot write a computer program that is guaranteed to halt to decide the question for all L(G). Unrestricted Grammar Equivalent to: Turing machine von Neumann machine C++, Java That is, can compute any computable . | Programming Languages 2nd edition Tucker and Noonan Chapter 3 Lexical and Syntactic Analysis Syntactic sugar causes cancer of the semicolon. A. Perlis Contents Chomsky Hierarchy Lexical Analysis Syntactic Analysis Chomsky Hierarchy Regular grammar -- least powerful Context-free grammar (BNF) Context-sensitive grammar Unrestricted grammar Regular Grammar Simplest; least powerful Equivalent to: Regular expression Finite-state automaton Right regular grammar: T*, B N A → B A → Example Integer → 0 Integer | 1 Integer | . | 9 Integer | 0 | 1 | . | 9 Regular Grammars Left regular grammar: equivalent Used in construction of tokenizers Less powerful than context-free grammars Not a regular language { aⁿ bⁿ | n ≥ 1 } ., cannot balance: ( ), { }, begin end Context-free Grammars BNF a stylized form of CFG Equivalent to a pushdown automaton For a wide class of unambiguous CFGs, there are table-driven, linear time parsers Context-Sensitive Grammars Production: α →
