Kiến trúc máy tính và hợp ngữ - Chapter 3: Lexical and syntactic analysis

Programming Languages2nd editionTucker and NoonanChapter 3Lexical and Syntactic AnalysisSyntactic sugar causes cancer of the semicolon. A. PerlisContents3.1 Chomsky Hierarchy3.2 Lexical Analysis3.3 Syntactic Analysis3.1 Chomsky HierarchyRegular grammar -- least powerfulContext-free grammar (BNF)Context-sensitive grammarUnrestricted grammarRegular GrammarSimplest; least powerful Equivalent to:Regular expressionFinite-state automatonRight regular grammar:   T*, B  NA →  BA →  ExampleInteger → 0 Integer | 1 Integer | ... | 9 Integer | 0 | 1 | ... | 9Regular GrammarsLeft regular grammar: equivalentUsed in construction of tokenizersLess powerful than context-free grammarsNot a regular language{ aⁿ bⁿ | n ≥ 1 }i.e., cannot balance: ( ), { }, begin endContext-free GrammarsBNF a stylized form of CFGEquivalent to a pushdown automatonFor a wide class of unambiguous CFGs, there are table-driven, linear time parsersContext-Sensitive GrammarsProduction: α → β |α| ≤ |β| α, β  (N  T)*ie, lefthand side can be composed of strings of terminals and nonterminalsUndecidable Properties of CSGsGiven a string  and grammar G:   L(G)L(G) is non-emptyDefn: Undecidable means that you cannot write a computer program that is guaranteed to halt to decide the question for all   L(G).Unrestricted GrammarEquivalent to:Turing machinevon Neumann machineC++, JavaThat is, can compute any computable function.