CODEWITHSUNDEEP
parsingrecursiongrammar
John Peterson
John Peterson

Reputation: 55

Recursive grammar for the language of strings

I was given the following task:

Write a recursive grammar for the language of strings of one or more letters. The first letter of each string must be uppercase, and all other letters in the string must be lowercase.

After reading the chapter on grammar, and exploring some examples, this is my attempt:

<goodString> =<UpCh>|<UpCh> <ch> 

<UpCh> = A|B|C...|Z

<ch> = a|b|c...|z

or maybe

<goodString> =<UpCh>|<goodString> <ch>

<UpCh> = A|B|C...|Z

<ch> = a|b|c...|z

Is this right? If not, what did I do wrong?

Upvotes: 2

Views: 785

Answers (1)

Jerry Coffin
Jerry Coffin

Reputation: 490048

Right now your grammar isn't recursive. A recursive grammar would/will include at least one production that invokes itself (directly or indirectly) on the right side.

In this case, the obvious place to use that would be "an indefinite number of lower case letters". For that I'd define a lower case string (or whatever) as either nil, or a lower case string followed by a lower case letter. Then your word will be an upper case letter followed by a lower case string.

Note that for a case like this, you can define the lower case string as a character followed by a string, or as a string followed by a character. These are known as right recursive and left recursive respectively. If there's any chance you'll ever implement the grammar, you probably want to know that you want the right recursive form for a recursive descent parser, but generally prefer the left recursive form for a bottom up parser (such as many generators such as yacc, Bison, byacc, etc., produce).

Upvotes: 3

Related Questions