Compiler

According to the length \(n\) of the program measured by tokens, it construct a triangle table with length \(n\).

T
T T
T T T
T T T T
a a b b

Invented by Jay Earley, it is used to parse CFG. It can parse all CFG, while LR and LL can only handle restricted classes. It executes in O(n³) where n is length of string, O(n²) for unambiguous grammars, and linear for almost all LR(k) grammars. It performs particularly well for left-recursive grammars.

Notation: for every input position, it generates a state set (called S(k) for input position k), consisting of:

• the production rule using
• the position in that production rule
• the original position in the string

The parser repeatedly executes three options:

• Prediction: for every state in S(k) of the form \(X->\alpha \cdot Y \beta\), add \(Y->\cdot \gamma\) to S(k)
• Scanning: for every state in S(k) of form \(Y -> \alpha \cdot a \beta\), add \(X -> \alpha a \cdot \beta\) to S(k+1)
• Completion: for every state in S(k) of the form \(X -> \gammar \cdot\), and … (TODO), add \(Y -> \alpha X \cdot \beta\) to S(k)

  procedure PREDICTOR((A → α•B, i), j, grammar)
    for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do
      ADD-TO-SET((B → •γ, j), chart[ j])
  procedure SCANNER((A → α•B, i), j)
    if B ⊂ PARTS-OF-SPEECH(word[j]) then
      ADD-TO-SET((B → word[j], i), chart[j + 1])
  procedure COMPLETER((B → γ•, j), k)
    for each (A → α•Bβ, i) in chart[j] do
      ADD-TO-SET((A → αB•β, i), chart[k])

• -C: do not discard comments
• -nostdinc: do not search standard system directory for header files, use only -I directories.
• D, U, -undef: predefine or un-predefine macros. Note that this is pre-defined macros only, will not affect the macros in code
• -dM: instead of normal preprocessed program, output all the #define directives (including both pre-defined and user-defined)
• -dD: output preprocessed + user-defined define directive
• -dI: output preprocessed + #include directive
• -M, -MM, MD, MMD: There are also some commands dealing with source code dependencies

The simple form is a single identifier. The input is scanned sequentially. Each time a substitution happens, the result is added to the front of remaining text, allowing nested expansion. This also means, if later the nested macro is redefined to another value, the new value is always used.

In terms of macros with arguments, the substitution checks for comma to separate parameters. The parameters can be any arbitrary expression that does not contain comma. However, a single parameter can have comma. This is done by matching parenthesis for each parameter, i.e. the parameter must have balanced parenthesis, and a comma inside parenthesis does not end the parameter. However, the brackets and braces are not checked for balance. Like the simple macros, the output is added to the front of remaining text and get expanded accordingly.

When defining a argument macro, the argument names (should be specifically the open parenthesis) must follow macro name immediately without any space.

The evaluation of the node will benefit from the attributes. It is categories into synthesized attributes and inherited attributes. This is mentioned in the syntax-directed translation part of dragon book, so I don't really think it is syntax related.

This seems to be synonyms of attribute grammar. Wikipedia has an example of using it to resolve the plural verbs, e.g. John likes children. The grammar does make perfect sense to me though.

Sentence → Subject + number Predicate+number
Subject + number → Noun + number
Predicate + number → Verb + number Object
Object → Noun + number
Noun + singular → John
Noun + singular → Mary
Noun + plural → children
Noun + plural → parents
Verb + singular → likes
Verb + plural → like
Verb + singular → helps
Verb + plural → help

Two level grammar is used to generate another formal grammar. This is like meta programming, or abstraction. One advantage is that is can define a grammar with infinite number of rules, due that it is generated.

For the context-sensitive language {a^nb^nc^n}, the two level grammar is:

N ::= 1 | N1
X ::= a | b

Together with the schema:

S ::= <a^N><b^N><c^N>
<X^{N1}> ::= <X^N> X
<X^1> ::= X

It is named by its inventor, and used in the language ALGOL 68. It is also called vW-grammar, or W-grammar. Also note that it is too powerful and also impractical as well.

It is:

• affix grammar
• two-level grammar

The ALGOL 68 grammar:

a) program : open symbol, standard prelude,
     library prelude option, particular program, exit,
     library postlude option, standard postlude, close symbol.
b) standard prelude : declaration prelude sequence.
c) library prelude : declaration prelude sequence.
d) particular program :
     label sequence option, strong CLOSED void clause.
e) exit : go on symbol, letter e letter x letter i letter t, label symbol.
f) library postlude : statement interlude.
g) standard postlude : strong void clause train

The idea is simple: provide non-terminal symbols with attributes (or affixes) that pass information between nodes of parse tree. This seems essentially to be using syntax to specify semantics. E.g. variable := value is in-complete but instead REF TYPE variable := TYPE value.

LR cannot handle nondeteministic and ambiguous grammars. GLR allows shift/reduce and reduce/reduce conflicts. It does that by doing a breadth-first-search, whenever multiple choices can be taken. All the choices are explored simultaneously, until it reach an error state or merge into another (if they generate the same set of symbols).

This is a easily misunderstood problem. There's a old 1989 discussion on comp.lang.misc:

• https://groups.google.com/forum/#!topic/comp.lang.misc/MCZmQv56--Q

So here's my understanding: C language is context sensitive:

• an identifier must be previously defined, to be able to be a typedef-name
  • this is different from an undeclared variable: an identifier is always parsed into category "identifier", regardless of whether it has been declared. However, undefined typedefs are ambiguous.
  • typedef-name : identifier
• else must match the closest else-less if
• continue and break must be in correct context

On the other hand, the C grammar in the back of K&R, is context-free, because it is in BNF format. However, it accepts more than C language.

Also in another word, the K&R grammar generates valid C programs and some invalid ones, and those are detected by the semantic analyzer.

A word about ambiguity: it does not affect the language it generates, but only generates (or recognizes) the same sentence in multiple ways.

Yacc generates LALR(1) parser. The C grammar is not a no-feedback yacc-able grammar. The thing is, when the lexer is trying the rule "typedef-name: identifier", the lexer should answer "typedef-name" iff the identifier happens to be a typedef name.. We also need to make sure that it tries this rule before the rule "primary: identifier". So the implementation is to add a predicate "identifier-is-really-typedef" to the action of the rule "typedef-name".

K&R has the following sentence:

With one further change, namely deleting the production typedef-name: identifier and making typedef-name a terminal symbol, this grammar is acceptable to the YACC parser-generator.

This is the fundamental reason why the yacc grammar differs from the K&R grammar. The typedef-name a terminal symbol also means that, C does have a infinite number of (non?-)terminals.

David Gudeman in that mailing archive said one sentence:

The grammar is intended to show syntactic categories with semantic attachment.

And someone said:

we generally do not write grammars that accept only strictly correct inputs. Instead, we take some shortcuts and patch things up via semantics.

Chris Torek:

Strictly speaking (as long as you stick with `typedef produces a new type specifier'), C's grammar is not context free; but it is indeed not seriously `screwed up'. Perfect generators are not necessary, and a language `close enough to C' exists that can be parsed simply.

Since typedef produce a new "terminal", can we really say C grammar has infinite number of "terminals", and the definition of Chomsky hierarchy context free grammar does not hold for C grammar.

The C grammar in back of K&R by no means is the correct C grammar, or the grammar used in compiler implementation.

The typedef-name problem is also called The Lexer Hack. There must be a feedback loop from the parser to insert the typedef-name into the symbol table, and the lexer will use this information to determine whether it is a typedef-name or token. The parser action must insert this table before the ,=; declarator terminator, because the lexer is allowed to lookahead 1 token, and the token might be an identifier.

• In Syntax Tree, interior nodes represent programming constructs.
• In parse tree, interior nodes represent non-terminals
• many non-terminals of a grammar represent programming constructs, but others are helpers of one sort of another, such as term, factors.
• In syntax tree, these helpers typically are not needed and hence dropped.

To conclude:

concrete syntax tree

the parse tree

concrete syntax

the underlying grammar of a parse tree

Some new understanding of them (quotes from dragon book):

CST

A parse tree pictorially shows how the start symbol of a grammar derives a string in the language.

AST

Abstract syntax trees, or simply syntax trees, differ from parse trees because superficial distinctions of form, unimportant for translation, do not appear in syntax trees.

That is to say, CST exactly reflect the grammar, and AST removes a lot of things but keep the structure. This includes:

• remove non-value-carrying leaves
• remove unary productions
• compress spines caused by left or right recursive grammar rules into explicit list nodes.

The implementation of AST is different for different parser designers. For example as the Clang fold said¹:

Clang’s AST is different from ASTs produced by some other compilers in that it closely resembles both the written C++ code and the C++ standard. For example, parenthesis expressions and compile time constants are available in an unreduced form in the AST. This makes Clang’s AST a good fit for refactoring tools.

var a = 2,
    b = (a + 2) * 3;

Here, the ( ) around a + 2 is not represented in the AST, because the structure of the tree, combined with operator precedence rules, absolutely implies that it must exist, and moreover a + 2 * 3 would have been a different tree structure. ^{2 , 3}

Estools ⁴ is a good collection of repos that have many interesting discussion threads about AST and CST.

Also, a post from semantic design ⁵, mentioned:

Typical parser generators force the grammar engineer to specify not only the grammar, but also to explicitly specify how to procedurally build the AST as well.

In contrast, DMS automatically builds a syntax tree, either a concrete tree ("CST", mainly for debugging, containing all the language tokens), or what amounts to an AST (for production, in which non-value carrying terminals are eliminated, useless unary productions are removed, and lists are formed).

A very good comparison on a lecture note ⁶.

A ::= A alpha | beta

A ::= beta R
R ::= alpha | epsilon

Recusrive descent parsing

• general form of top-down parsing
• may require backtracking

Predictive parsing

• a special case of recursive-descent parsing
• do not require backtracking
• By look ahead fixed number (usually 1) of tokens

LL(k)

A class of grammar, for which we can construct a predictive parser by looking k symbols ahead.

The general recursive descent parsing problem is:

void A() {
  choose an A-production
  for (i = 1 to k) {
    if (xi is nonterminal) call X();
    else if (xi = input symbol) advance_to_next_symbol();
    else error();
  }
}

This is non-deterministic since it begins with choose a production. To augment backtracking to the algorithm, we need:

• try different productions
• at error, return to the line of choose production
• we need a local variable to store where is the input symbol when choosing production.

Left recursive grammar can cause a recursive-descent parser (even the one with backtracking) into an infinite-loop. Because it try to expand A without consuming any input.

shift-reduce parsing

a general style of bottom-up parsing

LR grammar

the largest class of grammars for which shift-reduce parsers can be built

The bottom up parsing can think as reducing a string to the start symbol. At each reduction step, a substring is replaced by a non-terminal. Thus the key decisions are:

• when to reduce
• what production to apply

%precedence "then"
%precedence "else"

%right "then" "else"

  statement = ...
     | selection-statement

  statement-with-else = ...
     | selection-statement-with-else

  selection-statement = ...
     | IF ( expression ) statement
     | IF ( expression ) statement-with-else ELSE statement

  selection-statement-with-else = ...
     | IF ( expression ) statement-with-else ELSE statement-with-else

void items(G') {
  C=CLOSURE({S->.S'});
  repeat until no new {
    for (each set I in C) {
      for (each grammar symbol X) {
        add GOTO(I,X) to C}}}}

  while (true) {
    s = stack.top;
    a = next input;
    if (ACTION(s,a) = shift t) {
      stack.push(t)
      advance(a)
    } else if (ACTION(s,a) = reduce A to beta) {
      stack.pop(len(beta));
      t = stack.top
      stack.push(GOTO(t,A))
      output production A->beta
    } else if (ACTION=accept | error) {}
  }

• http://www.scottmcpeak.com/elkhound/

Elkhound is an ancient parser generator, and Elsa is the C++ parser built upon it. It is clean docs, maybe clean code, worth to check out.

It implements the Generalized LR (GLR) parsing, which works with any context-free grammars. LR parsers (like bison) requires the grammar to be LALR(1).

• GLR: https://en.wikipedia.org/wiki/GLR_parser

Parsing with arbitrary context-free grammars has two key advantages: (1) unbounded lookahead, and (2) support for ambiguous grammars. Both of them are achieved by allowing multiple potential parses to coexist for as long as necessary.

The downside, since it is more general, is slower performance.

A Commercial Parser Front end:

• http://www.semanticdesigns.com/Products/FrontEnds/CppFrontEnd.html

yacc & lex

generate LALR

bison & flex

open source for yacc, so also LALR

antlr

top down parser generator, generates recursive-descent parser