Re: Exercise 2.1.2 from Aho&Ulman The theory of Parsing textbook?

On Apr 21, 9:50 pm, Barb Knox <s...@xxxxxxxxx> wrote:
In article
<0a72f6c4-1337-4884-bb1c-a205b1fef...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
 Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:

"Construct CFG that generates all strings having equal number of a's
and b's"

My attempt:

X = 1 + aXa + aaX +Xaa + bXb + Xbb +bbX +YY
Y = 1 + (a+b)Y

looks too complicated for such concise problem statement. Any shorter
solution?

The difficulty isn't that it's too complicated, but that it's wrong.  
Your Y can be any string of a's and b's; the "YY" alternative in X does
*not* mean that the same Y string is replicated, but rather that 2
independent Y strings are concatenated.  So, your X grammar will accept
*any* string of a's and b's (e.g., with the first Y being empty, and the
second being any string of a's and b's).

Not only that but terms like aXa were also wrong. How about

Y = YaYbY + YbYaY + 1

.

Relevant Pages

  • Re: need simple parsing ability
    ... > sometimes a short string followed by an integer, ... Here's a pyparsing solution. ... then to the parse actions attached to the ... different bits of the grammar. ...
    (comp.lang.python)
  • Re: design a Condition class
    ... of grammars in pyparsing. ... # parse input string ... The resulting grammar expressions are fairly readable. ... by another word group of alphabetic characters, ...
    (comp.lang.python)
  • Re: An argument for the redundancy of truth
    ... settle where I suggested, it ought to settle - as the grammar of ... If you KNEW what a grammar was, THEN YOU WOULD KNOW this already, ... The purpose of a grammar is to define some structure on a string. ... AND EVERY GRAMMAR DETERMINES those truth-values. ...
    (sci.logic)
  • Re: Definition of Production
    ... rule to input string, ... `production' == `production rule'. ... Grammar productions are defined formally in Waite & Goos, ... of finite V strings, including the empty string). ...
    (comp.compilers)
  • Whats This Model of Computing Called?
    ... It's something that takes a sequence of symbols (a character string) as input, makes some faint whirring sounds for a while, and hopefully gives a sequence of symbols as output when it halts. ... But, in general, whatever it is, it can be described by an attributed grammar. ... But here's the idea I had: use this model of computing to compute the attribute strings themselves! ... Such strings, along with literal strings, can then be concatenated into one string, which may itself be processed by a parser specified by a nonterminal symbol. ...
    (comp.theory)