ITEC 380 2018fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

grammars, cont.

Review Grammars

• Parse tree.
  • Every internal node is a non-terminal;
  • every leaf is a terminal;
  • every branching reads directly from one of the rules in the grammar.

Recall: We write “→” for entire grammar rules, and “⇒” for individual derivations.

Examples:

• What is a grammar for an int literal, in (say) Java?
  What are examples of the data; then see if you can make a grammar (a data-definition).
• Compare here¹ In the link: Does Digits ⇒* 3__4? Show, or argue why not.
• What is a grammar for numeric arithmetic expressions?

• diagramming sentences is exactly the same as specifying parse trees (for English; they add different branches to encode some of the subtle/optional/complicated grammar rules about appositive gerund phrases² or whatever).
• Suppose Siri tells you [in monotone voice] “In one mile, turn left on too eighty one”. (Well, I misspelled “too”; it should be ...?)
• buffalo from Buffalo
• Some collected English ambiguities; we can decide whether some are syntactic, vs. “merely-semantically” ambiguous.
• Def'n: a grammar is ambiguous if one string has two different parse trees.
  The canonical programming-languages example, “dangling if”:

  int n = 0; if (A) then n = n+1 if (B) then n = n+1 else n = n+100

  Of course, as a programmer we should indent meaningfully. …Hey, our indentation looks like the syntax-tree we want to create! (turn your head sideways). Not a coincidence: just like a poet, we use the words and their layout on the page to reinforce the meaning of what we are trying to communicate.

  Solutions to the dangling-if problem include:

  • require curly-brackets always;
  • (equivalently: require “endif” or “end” or “fi” to end an if-without-else
  • only allow one single statement after `if` (but: allow block-statement as a type of statement);
  • add “elif” or “elseif” as keywords;
  • Require correct-indentation as part of the syntax(!)

New terms:

• the language a grammar defines.
• "parse": a function from string → parse-tree.
  (We'll take each "parse" to be relative to some existing grammar³.)
• ambiguous: If one string has two different (valid) parse-trees for it.
• don't confuse: the grammar(syntax), vs. semantics

Some things we may have noticed, in the reading:

• extended grammars that let you use handy things like “ ” or “ε” are nice, but we see they're just syntactic sugar.
• There can be multiple derivations corresponding to the same tree. I'll ask for the left-most derivation, esp. when you have a word processor to use. (On exams, I might prefer trees, to avoid writing.)
• There might be different grammars that are equivalent. In particular, the rule Digits → Digit Digits will parse the same strings that Digits → Digits Digit does. (one will have leftward-leaning parse trees and the other rightward).
• Take ITEC420 to talk about: when grammars are equivalent; converting (some) grammars to others fundamental limits on what grammars can express (and, some algorithms for parsing);

It is helpful to actually divide reading-a-program's-input into three phases:

• tokenizing (or "lexing"): a quick pass to chunk/group characters into higher leve. tokens, like identifiers, int-literals, string-literals, etc.

  While it is conceivable to omit this step, having grammar non-terminals of (say) “Digit” instead of “IntLiteral”, it would mean that the resulting parse tree would have three entire nodes for the literal “765”. Having a parse tree with that level of bushiness is not actually helpful when trying to work with the program.

• parsing: build the parse-tree.
• sanity-checking : look for literals that are larger than Integer.MAX_VALUE or Long.MAX_VALUE; maybe look keywords being used where just identifiers were expected; look for for unbound-identifiers; unreachable return-statemnts, etc. These are all things that are easier to do once the parse tree has been built.

In Programming Languages and Interpretation §1.4, Shriram Krishnamurthi argues that what I here call “parsing” can benefit from being decomposed into two smaller phases: reading the tokenized input into a simple hierarchy (perhaps just based on matched parentheses), and then full parsing/validating of the grammar; this second part becomes easier since the input is already in structure-rich form that is easy for the parser/validator to work with. Indeed, using LISP/scheme/racket's read to create a basic tree (S-Expression) is both highly-reusable in many contexts, and significantly helpful in those contexts — the mark of a good decomposition of tasks.

Note that the grammar for Java doesn't quite match "does the program compile" — the CFG doesn't catch using-an-undefined-variable, for example. (CFG grammars cannot capture this!) This fact is usually ignored, and most everybody will say "yes there is a CFG for Java," even though the set of legal (compilable) programs is determined

  S → aS
  S → b

A Language: a set of strings. (e.g. the set of all valid Java programs — an infinite set). What language does the above grammar define?

The language defined by a grammar: the set of all strings derivable. To show that a string is in the grammar, show me a derivation (possibly a left-most derivation); equivalently show me a parse-tree.

To specify a grammar, you officially need four things:

• What are the terminals symbols?
  (Our default: uppercase.)
• What are the non-terminal symbols?
  (Our default: lowercase.)
• What are the rules? A list of pairs of strings.
  Written as lhs → rhs
• What is the start-nonterminal, for the grammar?
  (our convention: the first rule's left-hand-side is the start symbol.)

Most commonly seen: context-free grammars, “CFG”: every rule's left-hand-side is a single non-terminal.
BNF: same as CFG, but use "::=" instead of →, and "|".

regular grammar: each right-hand-side has at most one non-terminal. (equivalent to regular expresssions, in expressibility: A langauge is generated by some regular grammar if, and only if, there is a regular expression that matches exactly the strings in a language. We'll say "the language is regular", w/o committing ourselves to any particular grammar or reg.exp. (Note that these are regular expressions without back-references!)

A grammar for

 
<integer> →  <digit><integer> | <digit>
<digit> →  0 | 1 | 2 | 3 ... | 9

<ident> →  <letter>|<letter><letterOrDigitSeq>

<letterOrDigitSeq> →  <letterOrDigit>|<letterOrDigit><letterOrDigitSeq>

<letterOrDigit> →  <letter> | <digit>

<letter> →  a | b | c ...

EBNF: Allow shorthands in BNF: For a non-terminal A,

• 0-or-more As: A* (or, A…)
• 1-or-more As: A+
• 0-or-1 (optional) α/A: A? or [α]

Example: Write a simple grammar that matches arithmetic-expressions:

3 + 7
143
3 + 7 + 99
29 + 8 * 3

We say that a grammar is ambiguous iff one string has two different (legal) parse trees. We don't like ambiguity. There are several solutions:

• Book example: add some additional nonterminals to the grammar so that we can only generate one of those two parse trees. That is, make the grammar more complicated so that the “correct precedence” always auto-happens.

  This extra nonterminal is usually called a “Term” and/or a “Factor” in this particular example, and it corresponds to the product of 1-or-more expressions. The grammar is carefully constructed so that + only occurs between entire Terms, so Terms are already parse-trees before + comes along.

  See: www.csse.monash.edu.au/~lloyd/tildeProgLang/Grammar/Arith-Exp/

• Java: Leave the grammar simple, but then add a of rules about operator precedence (46 operators, with 14 levels of precedence!). This extra knowledge is needed to build the correct parse tree, even though it's not part of the context-free grammer by itself.
• Lisp/scheme/racket: keep the syntax simple, obviating any ambiguity (at the price of the programmer sometimes adding parentheses where other languages rely on intuition).

Task: Can you make a grammar Ada's int-literals, which allow underscores (similar to Java 8), except that: You can't start or end with an underscore, and can't have two in a row.

Can you make a grammar for XML?

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu