Unformatted text preview:

1CS780(Prasad) L6CFG 1Context-free GrammarsAdapted from material by:Prof. Alex Aiken and Prof. George Necula(UCB)CS780(Prasad) L6CFG 2Outline¾Regular languages revisited¾Parser overview¾Context-free grammars (CFGs)¾Derivations¾AmbiguityCS780(Prasad) L6CFG 3Regularity• Languages requiring counting modulo a fixed number are regular.• Finite automaton cannot count without limit or remember number of times it has visited a particular state.• Many languages are not regular. E.g., Language of balanced parentheses is not regular.{}() | 0iii ≥CS780(Prasad) L6CFG 4Parsing : Example• Coolif x = y then 1 else 2 fi• Parser inputIF ID = ID THEN INT ELSE INT FI• Parser outputIF-THEN-ELSE=IDIDINTINT2CS780(Prasad) L6CFG 5Input to and output of a parser-( )123.3 23.6+minus_opleft_paren_opnum(123.3)plus_opnum(23.6)right_paren_opToken Stream Parse TreeInput: - (123.3 + 23.6)Syntax Analyzer (Parser)CS780(Prasad) L6CFG 6Context-Free Grammars• Programming language constructs have recursive structure.¾An EXPR isif EXPR then EXPR else EXPR fiwhile EXPR loop EXPR pool…• Context-free grammars are a natural notation for this recursive structure.Iteration : Regular ExpressionTail Recursion : Regular GrammarGeneral Recursion : Context-free GrammarCS780(Prasad) L6CFG 7CFG = (N, T, P, S)• N : Finite set of variables/non-terminals• T : Alphabet/Finite set of terminals• P : Finite set of rules/productions• S : Start symbol*T)(NN A A :RuleTNNS∪∈∈→=∩∈ωωφCS780(Prasad) L6CFG 8• a* represents a context-free language because we can write a CFG for it.••ContextContext--freeness:freeness: An A-rule can be applied whenever A occurs in a string, irrespective of the context (that is, non-terminals and terminals around A).Cf. context-sensitive grammar (“declare-use”))},,{},{},({ SaSSSaS →→ε3CS780(Prasad) L6CFG 9Examples of CFGs• A fragment of Cool:EXPR if EXPR then EXPR else EXPR fi| while EXPR loop EXPR pool|id→–Non-terminals are written in upper-case.–Terminals are in lower-case.–The start symbol is the left-hand side of the first production.CS780(Prasad) L6CFG 10• Balanced Parenthesis GrammarS → ( S ) S | ε• Simple arithmetic expressions:()EE E|E + E|E|id→∗CS780(Prasad) L6CFG 11Example: Hierarchical ScopeProcedure foo(integer m, integer n, integer j) {for i = 1 to n do { if (i == j) {j = j + 1; m = i*j;}for k = i to n {m = m + k;}}}• Balanced Parentheses Problem– Example: {{}{{{}{{}}}}}CS780(Prasad) L6CFG 12• One-step Derivation • w is derivable from v in CFG, if there is a finite sequence of rule applications such that:From CFG to Languageωω→⇒A vuuAvwwwvn=⇒⇒⇒ ...14CS780(Prasad) L6CFG 13Let G=(N, Τ, P, S) be a CFG.•is a sentential form, if .•is a sentence, if .•The language of G, L(G) = *)TN( ∪∈wwS*G⇒*T∈wwS*G⇒}S|*T{*Gww ⇒∈}0|{)()},,{},,{},{{≥=→→=nbaGLSaSbSSbaSGnnεCS780(Prasad) L6CFG 14Cool Example • Some “terminal strings” in the Cool language.idif id then id else id fiwhile id loop id poolif while id loop id pool then id else idif if id then id else id fi then id else id fiCS780(Prasad) L6CFG 15Notes on Parser• Parser checks the membership in a language + constructs a parse tree for the input.• Parser must handle errors gracefully.• Parser generators implement CFG’s (e.g., bison).• Form of the grammar is important.¾Many grammars generate the same language.¾Tools are sensitive to the grammar.CS780(Prasad) L6CFG 16Derivations and Parse Trees•Aderivation is a sequence of production applications.• A derivation can be drawn as a tree¾Start symbol is the tree’s root¾For a production add children to (parent) node 1 nXYY→ L X1 nYYL5CS780(Prasad) L6CFG 17Derivation Example•Grammar• StringE E+E | E E | (E) | id→∗id id + id∗CS780(Prasad) L6CFG 18DerivationEE+EEE+Eid E + Eid id + Eid id + id→→∗→∗→∗→∗EEEEE+id*ididCS780(Prasad) L6CFG 19Derivation in Detail (1)EECS780(Prasad) L6CFG 20Derivation in Detail (2)EE+E→EE E+6CS780(Prasad) L6CFG 21Derivation in Detail (3)EEEE+EE+→∗→EEEEE+*CS780(Prasad) L6CFG 22Derivation in Detail (4)EE+EEE+Eid E + E→∗→→∗EEEEE+*idCS780(Prasad) L6CFG 23Derivation in Detail (5)EE+EEE+Eid E + id id + EE→∗→→∗→∗EEEEE+*ididCS780(Prasad) L6CFG 24Derivation in Detail (6)EE+EEE+Eid E + Eid id + Eid id + id→→∗→∗→→∗∗EEEEE+id*idid7CS780(Prasad) L6CFG 25Notes on Derivations• A parse tree has¾Terminals at the leaves.¾Non-terminals at the interior nodes.•An in-order traversal of the leaves is the original input.• The parse tree shows the association of operations, the input string does not.CS780(Prasad) L6CFG 26Left-most and Right-most Derivations• The previous example is a left-most derivation.¾ At each step, replace the left-most non-terminal.• There is an equivalent notion of a right-most derivation.EE+EE+idEE + idEid + idid id + id→→→∗→∗→∗CS780(Prasad) L6CFG 27Right-most Derivation in Detail (1)EECS780(Prasad) L6CFG 28Right-most Derivation in Detail (2)EE+E→EE E+8CS780(Prasad) L6CFG 29Right-most Derivation in Detail (3)idEE+EE+→→EE E+idCS780(Prasad) L6CFG 30Right-most Derivation in Detail (4)EE+EE+idEE + id→∗→→EEEEE+id*CS780(Prasad) L6CFG 31Right-most Derivation in Detail (5)EE+EE+idEE E+ idid + id→→→∗∗→EEEEE+id*idCS780(Prasad) L6CFG 32Right-most Derivation in Detail (6)EE+EE+idEE + idEid + idid id + id→∗→→→∗→∗EEEEE+id*idid9CS780(Prasad) L6CFG 33Summary of Derivations• Note that right-most and left-most derivations have the same parse tree; the difference is the order in which the branches are added.• We are not just interested in whether s ε L(G)¾ We need a parse tree for s.• A derivation defines a parse tree, but one parse tree may have many associated derivations.• Left-most and right-most derivations are important in parser implementation.CS780(Prasad) L6CFG 34Ambiguity This string has two parse trees.EEEEE*id +ididEEEEE+id*ididCS780(Prasad) L6CFG 35• A grammar is ambiguous if it has more than one parse tree for a string.• Ambiguity is BAD because it leaves meaning of some programs ill-defined.• Ambiguity can be avoided by rewriting the grammar.¾Interprets non-fully parenthesized expression, giving precedence to * over +.'''EEE | EE id E' | id |


View Full Document

Wright CS 780 - Context-free Grammars

Download Context-free Grammars
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Context-free Grammars and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Context-free Grammars 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?