Tue, 7 Sep 1993 23:15:33 GMT

Related articles |
---|

Opeartor-precedence v.s. LL(1) ejxue@ntu.ac.sg (1993-08-28) |

Re: Operator-precedence v.s. LL(1) tfj@apusapus.demon.co.uk (1993-08-29) |

Re: Operator-precedence v.s. LL(1) bart@majestix.cs.uoregon.edu (1993-08-30) |

Re: Operator-precedence v.s. LL(1) spencer@cwis.unomaha.edu (1993-09-07) |

Re: Operator-precedence v.s. LL(1) dww@cli.com (1993-09-07) |

Newsgroups: | comp.compilers |

From: | dww@cli.com (Debbie Weber-Wulff) |

Keywords: | parse, LL(1) |

Organization: | Technische Fachhochschule Berlin, visiting at Computational Logic, Inc |

References: | 93-08-111 93-09-019 |

Date: | Tue, 7 Sep 1993 23:15:33 GMT |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.