Re: BNF DEFINITION - help!

<banks@iowasp.physics.uiowa.edu> wrote:
> Using character set C={a,b} write a BNF definition for the language
>consisting of all strings with odd length whose first and middle characters
>are the same.


ellard@bbn.com (Dan Ellard) writes:
>In a yacc-like syntax:
>S : a middleA a // an "a" followed by something
> | a middleA b // with an "a" in the middle.
> // followed by any single char.
> | b middleB a // a "b" followed by something
> | b middleB b // with a "b" in the middle,
> // followed by any single char.
> | a
> | b
> ;
>middleA : a middleA a
> | a middleA b
> | b middleA a
> | b middleA b
> | a
> ;
>middleB : a middleB a
> | a middleB b
> | b middleB a
> | b middleB b
> | b
> ;


This can be made simpler if you are willing to use one more non-terminal:


S : a A X
| b B X
| X
;


A : X A X
| a
;


B : X B X
| b
;


X : a
| b
;


--
Mark Biggar
mab@wdl.loral.com
[I think we can now consider this homework problem solved. -John]
--

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