Compiler Designing W03L03 & 04

Derivation and Ambiguity

  • A derivation of a string for a grammar is a sequence of production rule applications that transforms the start symbol into the string.
  • A leftmost derivation is the one where at each step the leftmost non-terminal symbol is rewritten and likewise for rightmost derivation.
  • When there are two or  more parse trees for the same input the language is ambiguous. For example, id+id*id.
  • Ambiguity can be removed by rewriting grammar.
  • A better explanation is here.

Compiler Designing W03L01 & 02

Introduction To Parsing and Context Free Language

  • The sequence of tokens generated by scanner are given to parser as input, which produces parse tree.
  • In a parse tree, leaves are terminals or epsilon and internal nodes are non-terminals and root is the start symbol.
  • Context-free language plays an important role while creating a parse tree.
  • The degree of expression of formal languages:
    • Recursively enumerable language (Strongest)
    • Context Sensitive language
    • Context Free language
    • Regular language (Weakest)
  • A CFG is a 4-tuple grammar: G=(V, ∑, R, S)
    • V: a finite set containing non-terminal symbols.
    • ∑: a finite set disjoint from V and defined by G.
    • R: rules of production defined by G.
    • S: Element of V, usually the left symbol of the first production rule.
  • For example, these are some production rules of some CFL

S –> AB; S –> ASB; A –> a; B –> b

here a, b are terminals; A, B and S are non-terminals and S is the start symbol.

  • Regular languages are implemented using FA, having no memory element. no rule like: aibi can exist, while context free languages are implemented using pushdown automata, having a stack memory in addition.