Re: Operator-precedence v.s. LL(1)

A poster asked for the relationship between a member of a language and a
grammar. As someone who is attempting to do mechanical verification of a
parser I feel called on to respond:


[I like to use Hopcroft/Ullman and call the thing I want to test for
language membership a tape. This is a list of tokens which has been lexed,
sieved and otherwise coerced into being a sequence of "terminal symbols".]


A tape is said to belong to a grammar if it can be derived from the axiom
of the grammar, usually written as


      S =*=> w,


where S is the axiom and w the tape.


There can be any number of derivations (i.e. sequences of names of
productions that are applied) that will produce the same tree (which you
get by making left hand sides roots and right hand sides siblings in the
order in which they occur and glueing them together to make trees). There
are some interesting derivations, namely the left and the right
derivations, which always fuss with the leftmost or the rightmost
non-terminal in the sentential form (which is just a magic word for the
leaves of a cut through a derivation tree). But finding a derivation tree
in a top-down way tends to get exponential :-), so people have been
looking for ways to do this linearly. LL grammars are ones that make
finding a left derivation linear, LR for right derivations.


So the relationship from this point of view is: a tape is the same as the
leaves of a derivation tree from the axiom of the grammar.


A table-driven LR-parser is a program that takes a tape and a grammar,
generates a parsing table from the grammar, and traces _backwards_ through
a right derivation for the tape. It keeps some information around on the
symbol stack that, when concatenated with the remaining input, just
happens to be a sentential form for a right derivation. The first
"configuration" contains the tape corresponding to the final sentential
form, the last one just has the axiom on the stack (which is the first
sentential form [sort of a Jesus-ordering: the last shall be first and the
first shall be last:-)]).


If we collect up all the reductions done during parsing, we get the parse,
which is exactly the reverse of the right derivation. If the last
reduction is the axiom, we win, and know that the tape is a member of the
language of the grammar; if we stop because of the table signalling an
error or some such, the tape is not in the language of the grammar.


The relationship from here is that if the tape is in the language of the
grammar, the parser will produce a parse for it, i.e. recognize it. This
is succinctly given in the well-known theorem


        is-well-formed-grammar (g)
    & is-in-alphabet (tape, g)
  => parser-recognizes (tape, g) <=> is-in-language (tape, g)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.