Ch3 - Lecture 5 - Syntax & Semantics_Part 2.pdf

Chapter 3: Describing Syntax and Semantics Lectures # 5 Prof. Nidal F. Shilbayeh Dr. Asim Abdallah Elshiekh  Chapter 3 Topics Definitions Tokens and lexemes Formal Definition of La...

Chapter 3: Describing Syntax and Semantics Lectures # 5 Prof. Nidal F. Shilbayeh Dr. Asim Abdallah Elshiekh  Chapter 3 Topics Definitions Tokens and lexemes Formal Definition of Languages Formal Methods of Describing Syntax  Context Free Grammar (CFG)  Backus-Naur Form (BNF)  Derivation  Parse Trees An Ambiguous Expression Grammar Presidency and associativity of grammars Syntax Graphs Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 2  Derivation A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence. In each step of a derivation, exactly one nonterminal is expanded. Every string of symbols in a derivation is a sentential form. A sentential form may contain terminal and nonterminal symbols. A sentence is a sentential form that has only terminal symbols. Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 3  Types of Derivations Leftmost derivation: a derivation in which the leftmost nonterminal in the sentential form is always the one that is expanded. Rightmost derivation: a derivation in which the rightmost nonterminal in the sentential form is always the one that is expanded. A derivation may be neither leftmost nor rightmost. Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 4  An Example Grammar | ; = a | b | c | d + | - | const Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 5  An Example Derivation Using the above grammar derive the following sentence: a = b + const    =  a = Sentential Forms  a = +  a = +  a = b +  a = b + const Sentence Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 6  Parse Trees Parse tree is a well-defined representation of a syntactic structure of a sentence. A parse tree is a tree with the following properties: 1) Root is labeled with the starting symbol; = 2) Each leaf is labeled with a terminal symbol (token); a + 3) Each internal node is labeled with a const nonterminal symbol; b Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 7  Parse Tree vs Derivation    =  a =  a = +  a = +  a = b +  a = b + const Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 8  Ambiguous Grammars A grammar is ambiguous if and only if it generates a sentential form that has 2 or more distinct parse trees. Example: Using the sentence const – const/const, prove that the following expression grammar is ambiguous: | const / | - Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 9  An Ambiguous Expression Grammar The sentence: const – const/const | const / | - const - const / const const - const / const Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 10  Indicating Precedence If we use the parse tree to indicate precedence levels of the operators, we can avoid ambiguity. - | /const | const - / const const const Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 11  Associativity of Operators Operator associativity can also be indicated by a grammar. The following tree is left associative: + | * const | const + 5 Produce the expression: (3 + 4) + 5 + 4 3 Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 12  Associativity of Operators (cont.) Suppose we reverse the order of and on the RHS of the first rule: + | * const | const The tree corresponds to: 3 + (4 + 5), meaning + is now right associative. Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 13  Rule of thumb for associativity A left recursive production results in left associativity  EE+T (+ is left associative) A right recursive production results in right associativity  ET+E (+ is right associative) Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 14  Extended BNF (EBNF) Optional parts are placed in brackets [ ]. ident [()] BNF: ident | ident() Alternative parts of RHSs are placed inside parentheses and separated via vertical bars. (+|-) const BNF: + const | - const Repetitions (0 or more) are placed inside braces { }. letter {letter|digit} BNF: (letter|digit) | letter Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 15  BNF and EBNF BNF + | - | * | / | EBNF {(+|-)} {(*|/)} Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 16  Syntax Graphs Syntax graphs use directed graphs to represent syntax graphically.  Terminals are placed in circles.  Nonterminals are placed in rectangles.  Circles and rectangles are connected with lines with arrowheads. Pascal type declarations Chapter 3: Describing Syntax and Semantics Prof. Nidal F. Shilbayeh, Dr. Asim Abdallah 17