Re: Top down parsing

amitsaraff@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 ?

The trick lies in the statement that the production S->aSa is tried
first, a recursive descent parser will only work in this case for an
even no. of inputs (try constructing the parse tree and look at the
discrepancy found for strings of length n where n/2 is odd.)

In other words, a "top down parse with backtracking" can't recognize
grammar

S -> aSa | aa

correctly?

.

Relevant Pages

  • 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)
  • Re: Problem with a derivation tree
    ... S -> aSa | aa ... It is quoted that a "top down parse with backtracking" can establish ... The grammar he's fantasizing is ...
    (sci.math)
  • 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)
  • 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)