Kiến trúc máy tính và hợp ngữ - Chapter 2: Syntax a language that is simple to parse for the compiler is also simple to parse for the human programmer

Programming Languages2nd editionTucker and NoonanChapter 2SyntaxA language that is simple to parse for the compiler is also simple to parse for the human programmer. N. WirthContents2.1 Grammars 2.1.1 Backus-Naur Form 2.1.2 Derivations 2.1.3 Parse Trees 2.1.4 Associativity and Precedence 2.1.5 Ambiguous Grammars2.2 Extended BNF2.3 Syntax of a Small Language: Clite 2.3.1 Lexical Syntax 2.3.2 Concrete Syntax2.4 Compilers and Interpreters2.5 Linking Syntax and Semantics 2.5.1 Abstract Syntax 2.5.2 Abstract Syntax Trees 2.5.3 Abstract Syntax of CliteThinking about SyntaxThe syntax of a programming language is a precise description of all its grammatically correct programs.Precise syntax was first used with Algol 60, and has been used ever since.Three levels:Lexical syntaxConcrete syntaxAbstract syntaxLevels of SyntaxLexical syntax = all the basic symbols of the language (names, values, operators, etc.)Concrete syntax = rules for writing expressions, statements and programs.Abstract syntax = internal representation of the program, favoring content over form. E.g., C: if ( expr ) ... discard ( )Ada: if ( expr ) then discard then2.1 GrammarsA metalanguage is a language used to define other languages.A grammar is a metalanguage used to define the syntax of a language.Our interest: using grammars to define the syntax of a programming language.2.1.1 Backus-Naur Form (BNF)Stylized version of a context-free grammar (cf. Chomsky hierarchy)Sometimes called Backus Normal FormFirst used to define syntax of Algol 60Now used to define syntax of most major languages BNF GrammarSet of productions: P terminal symbols: T nonterminal symbols: N start symbol: A production has the form where and Example: Binary DigitsConsider the grammar: binaryDigit  0 binaryDigit  1or equivalently: binaryDigit  0 | 1Here, | is a metacharacter that separates alternatives.2.1.2 DerivationsConsider the grammar:Integer  Digit | Integer DigitDigit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9We can derive any unsigned integer, like 352, from this grammar. Derivation of 352 as an IntegerA 6-step process, starting with: IntegerDerivation of 352 (step 1)Use a grammar rule to enable each step:Integer  Integer DigitDerivation of 352 (steps 1-2)Replace a nonterminal by a right-hand side of one of its rules:Integer  Integer Digit  Integer 2Derivation of 352 (steps 1-3)Each step follows from the one before it.Integer  Integer Digit  Integer 2  Integer Digit 2Derivation of 352 (steps 1-4)Integer  Integer Digit  Integer 2  Integer Digit 2  Integer 5 2Derivation of 352 (steps 1-5)Integer  Integer Digit  Integer 2  Integer Digit 2  Integer 5 2  Digit 5 2Derivation of 352 (steps 1-6)You know you’re finished when there are only terminal symbols remaining.Integer  Integer Digit  Integer 2  Integer Digit 2  Integer 5 2  Digit 5 2  3 5 2A Different Derivation of 352Integer  Integer Digit  Integer Digit Digit  Digit Digit Digit  3 Digit Digit  3 5 Digit  3 5 2This is called a leftmost derivation, since at each step the leftmost nonterminal is replaced. (The first one was a rightmost derivation.)Notation for DerivationsInteger * 352 Means that 352 can be derived in a finite number of steps using the grammar for Integer.352  L(G) Means that 352 is a member of the language defined by grammar G.L(G) = {   T* | Integer *  } Means that the language defined by grammar G is the set of all symbol strings  that can be derived as an Integer.2.1.3 Parse TreesA parse tree is a graphical representation of a derivation.Each internal node of the tree corresponds to a step in the derivation.Each child of a node represents a right-hand side of a production.Each leaf node represents a symbol of the derived string, reading from left to right.E.g., The step Integer  Integer Digitappears in the parse tree as: IntegerIntegerDigitParse Tree for 352 as an IntegerFigure 2.1Arithmetic Expression GrammarThe following grammar defines the language of arithmetic expressions with 1-digit integers, addition, and subtraction.Expr  Expr + Term | Expr – Term | TermTerm  0 | ... | 9 | ( Expr )Parse of the String 5-4+3Figure 2.2