我被分配了以下任务:
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.
阅读语法章节并探索一些示例后,这是我的尝试:
<goodString> =<UpCh>|<UpCh> <ch>
<UpCh> = A|B|C...|Z
<ch> = a|b|c...|z
或者也许
<goodString> =<UpCh>|<goodString> <ch>
<UpCh> = A|B|C...|Z
<ch> = a|b|c...|z
这是对的吗?如果不是,我做错了什么?
最佳答案
现在你的语法不是递归的。递归语法将包括至少一个在右侧(直接或间接)调用自身的产生式。
在这种情况下,明显的使用位置是“无限数量的小写字母”。为此,我将小写字符串(或其他)定义为 nil,或小写字符串后跟小写字母。那么您的单词
将是一个大写字母后跟一个小写字符串。
请注意,对于这样的情况,您可以将小写字符串定义为一个字符后跟一个字符串,或者一个字符串后跟一个字符。这些分别称为右递归和左递归。如果您有机会实现该语法,您可能想知道您想要递归下降解析器的正确递归形式,但通常更喜欢自下而上解析器的左递归形式(例如许多生成器,例如 yacc 、Bison、byacc等出品)。
关于parsing - 字符串语言的递归语法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19353568/