Re: Problem with a derivation tree

On Sat, 21 Oct 2006 22:59:41 -0700, William Elliot
<marsh@xxxxxxxxxxxxxxxxxx> wrote:

On Sat, 21 Oct 2006 anandr86@xxxxxxxxx wrote:

In the book "Principles of compiler design, Aho Ullman" the
following exercise caught my attention. The grammar given is

S -> aSa | aa

It is quoted that a "top down parse with backtracking" can establish
the inputs with 2,4 or 8 a's but not 6 a's .... How is this possible ?

Inputs?! Don't get it.

Then why don't you let someone who understands the question try
replying?

S -> aSa -> aaSaa -> aaaaaa is an output.

The grammar he's fantasizing is
S -> SS | aa

Math isn't easy. To make it obscure, take computer courses. ;-)


************************

David C. Ullrich
.

Relevant Pages

  • Re: Parsing Expression Grammar
    ... problem with your grammar, it will simply not parse some inputs. ... The exception being, if the grammar is LL, then a PEG will ... I think it is possible to get a parser which nearly succeeds on all ...
    (comp.compilers)
  • Re: Top down parsing
    ... The grammar given is ... S -> aSa | aa ... It is quoted that a "top down parse with backtracking" can establish ...
    (comp.theory)
  • A few questions about parsing
    ... infrastructure (parse trees, intermediate forms etc). ... to create a parser that will receive the BNF grammar from libbnf and ... right recursions. ... What parser can parse this grammar? ...
    (comp.compilers)
  • Re: help with pyparsing
    ... I have the following lines that I would like to parse in python using ... I have the following grammar defn. ... Wordwill read any contiguous set of characters in the ... from pprint import pprint ...
    (comp.lang.python)
  • DCG parsing - Natural Language in Prolog
    ... I am learning grammar and parsing. ... BUT HOW CAN I EXTEND IT TO PARSE A MORE COMPLICATED ... The grammar rules to be covered are: ...
    (comp.lang.prolog)