DOC PREVIEW
U of I CS 421 - Lecture notes

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

OutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCS421 Lecture 13: Introduction to Grammars1Mark [email protected] of Illinois at Urbana-ChampaignJuly 6, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsObjectives and ReviewContext-Free GrammarsProperties of GrammarsMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsObjectivesYour goal for this lecture is to learn how to do the following things:◮Identify and explain the parts of a grammar.◮Define terminal, nonterminal, production, sentence,derivation, parse tree, left-recursive, ambiguous.◮Use a grammar to draw the parse tree of a sentence.◮Identify a grammar that is left-recursive.◮Know about ambiguous grammars:◮Be able to identify one when you see it.◮Be able to show ambiguity using derivations or parse trees.◮Know two strategies that could eliminate ambiguity.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsReminder: The Problem◮Computer programs are entered as a stream of ASCIIcharacters.4 + if x > 4 then 5 else 0◮We want to convert them into an Abstract Syntax TreeML code1 PlusExp(2 IntExp 4,3 IfExp(4 GtExp(VarExp "x",5 IntExp 4),6 IntExp 5,7 IntExp 0))Plus4IfGtx45 0Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsReminder: The SolutionCharacters Lexer Tokens Parser TreeThe conversion from strings to trees is accomplished in two steps.◮First, convert the stream of characters into a stream oftokens.◮This is called lexing or scanning.◮Turns characters into words and categorizes them.◮We did this in the last few lectures!◮Second, convert the stream of tokens into an abstract syntaxtree.◮This is called parsing.◮Turns words into sentences.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityContext-free GrammarsDef: A Context-free Grammar (CFG) is a 4-tuple:G = (N, Σ, P, S)where:1. N is a finite, nonempty set of symbols (non-terminals)2. Σ is a finite set of symbols (terminals)N ∩ Σ = ΦV ≡ N ∪ Σ (vocabulary)3. P is a finite subset of N × V∗(production rules)4. S ∈ N (Goal symbol or start symbol)Sometimes written as G = (V, Σ, P, S), N = V − ΣMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityExample Grammar: Arithmetic ExpressionsG = (N, Σ, P, S) where:N = {E, T , F }Σ = {(, ), +, ∗, id}P = {E → TE → E + TT → FT → T ∗ FF → idF → (E )}S = E.Note: P ⊆ N × V∗, whereV = N ∪ Σ ={E, T , F , (, ), +, ∗, id}Note: (A, α) ∈ P is usually writ-ten:A → αor A ::= αor A : αMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations of a GrammarDirectly Derives or =⇒ :If α and β are strings in V∗(vocabulary), then αdirectly derivesβ (written α =⇒ β) iff there is aproduction A → δ s.t.− A is a symbol in α− Substituting string δ for A in α produces thestring β.Canonical Derivation Step :The above derivation step is called rightmost if A isthe rightmost non-terminal in α. (Similarly,leftmost.)A rightmost derivation step is also called canonical.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations and Sentential FormsDerivation :A sequence of steps α0⇒ α1⇒ . . . ⇒ αn, whereα0= S is called a derivation. It is written S ⇒∗αn.If every derivation step is rightmost, then this is acanonical derivation.Sentential Form :Each αiin a derivation is called a sentential formofG.Sentences and the Language L(G) :A sentential form αiconsisting only of tokens (i.e.,terminals) is called a sentence of G.The language generated by G is the set of allsentences of G. It is denoted L(G).Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityParse Trees of a GrammarA Parse Tree for a grammar G is any tree in which:◮The root is labeled with S.◮Each leaf is labeled with a token a (a ∈ Σ) or ǫ (the emptystring)◮Each interior node is labeled by a non-terminal.◮If an interior node is labeled A and has children labeledX1, . . . , Xn, then A → X1. . . Xnis a production of G.◮If A → ǫ is a production in G, then a node labeled A mayhave a single child labeled ǫThe string formed by the leaf labels (left to right) is the yield ofthe parse tree.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityParse Trees (continued)◮An intermediate parse tree is the same as a parse treeexcept the leaves can be non-terminals.Notes:◮Every α ∈ L (G) is the yield of some parse tree. Why?◮Consider a derivation, α0⇒ α1⇒ . . . ⇒ αn, where αn∈L(G).For each αi, we can construct an intermediate parse tree.The last one will be the parse tree for the sentence αn.◮A parse tree ignores the order in which symbols are replacedto derive a string.Mark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityDerivations and Parse TreesExample: The rightmost derivation and the parse tree for:id * idE ⇒ T ⇒ T ∗ F ⇒ T ∗ id ⇒ F ∗ id ⇒ id ∗ idETT*FETTF*FidETTFid*FidMark Hills CS421 Lecture 13: Introduction to GrammarsOutlineObjectives and ReviewContext-Free GrammarsProperties of GrammarsCFGsExampleDerivations and Parse TreesAmbiguityUniqueness of DerivationsDerivations and Parse Trees◮Every parse tree has a unique derivation: Yes? No?◮Every parse tree has a unique rightmost derivation: Yes? No?◮Every parse tree has a unique leftmost derivation: Yes? No?Derivations and Parse Trees◮Every


View Full Document

U of I CS 421 - Lecture notes

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Lecture notes
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 Lecture notes 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 Lecture notes 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?