Skip to content

Latest commit

 

History

History
112 lines (77 loc) · 3.31 KB

013017.md

File metadata and controls

112 lines (77 loc) · 3.31 KB

CSCI 3366 Programming Languages

Spring 2017

R. Muller

Lecture Notes: 6

Today

More on Context-Free Grammars

  1. Ambiguity
  2. Precendence & Associativty

Last time we started working with context-free grammars. We mentioned in class that CFGs play a key role in the Chomsky Hierarchy and in the specification of the syntax of programming languages.

The Chomsky Hierarchy -- DCFLs can be parsed efficently

+-------------------------------------------------------------+
| Unrestricted                                                |
| +--------------------------------------------------------+  |
| | Context Sensitive                                      |  |
| | +---------------------------------------------------+  |  |
| | | Context Free                                      |  |  |
| | | +----------------------------------------------+  |  |  |
| | | | Determinisitic Context Free                  |  |  |  |
| | | | +-----------------------------------------+  |  |  |  |
| | | | | Regular                                 |  |  |  |  |
| | | | +-----------------------------------------+  |  |  |  |
| | | +----------------------------------------------+  |  |  |
| | +---------------------------------------------------+  |  |
| +--------------------------------------------------------+  |
+-------------------------------------------------------------+

1. Ambiguity

Reviewing our simple grammar for logical expressions

S ::= t | f | S || S | S && S | !S | ( S )

We found that there are sentences in L(S) with multiple left-most derivations.

w = t || t && t

S => S && S => S || S && S => t || S && S => t || t && S => t || t && t
S => S || S => t || S => t || S && S => t || t && S =>      t || t && t

For a grammar G, if there exists a w in L(G) such that there are more than one left-most (right-most) derivations, then the grammar is said to be ambiguous. Ambiguity is not a show-stopper for programming languages — one can write parsers for ambiguous grammars that take steps to chose the desired parse. Of the two parses above, we prefer the latter.

            &&                   ||
           /  \                 /  \
         ||    t               t    &&        the AST on the right reflects standard precedence
        /  \                       /  \
       t    t                     t    t

2. Precedence & Associativity

One can impose precedence and associativity preferencecs directly in the grammar for the concrete syntax

  • In order to give operator A higher precedence that operator B, introduce it further away from the start symbols;
  • Enforce left-associativity: x A x A x means (x A x) A x use left-recursion, and likewise for right.

We rewrite our concrete grammar.

E ::= E || T | T
T ::= T && F | F
F ::= t | f | !E | ( E )

Now to left-derive w = t || t && t

E => E || T => T || T => F || T => t || T 
  => t || T && F => t || F && F => t || t && F => t || t && t

The concrete and abstract syntaxes are

             E                        ||
           / | \                     /  \
          E  ||  T                  t     &&
          |    / | \                     /  \
          T   T  &&  F                  t    t
          |   |      |
          F   F      t
          |   |
          t   t