首先计算，遵循并预测EBNF表示法

Question

语法规则定义为：

• 整数文字是一个数字序列;
• 布尔文字是真或假的文字;
• 关键字是if，while或boolean文字之一;
• 变量是一个以字母开头，后跟字母或数字的字符串，不是关键字;
• 运算符是<=> = ==！= && ||之一= + - * <>
• 标点符号是（）{}，;字符。

根据描述，我用EBNF表示法写出语法如下：

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
int literal = digit {digit} ;
bool = "true" | "false" ;
keyword = "if" | "while" | bool ;
letter =  "A" | "B" | "C" | "D" | "E" | "F" | "G"  | "H" | "I" | "J" | "K" | "L" | "M" | "N"  | "O" | "P" |   
               "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" |
               "h" |   "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | 
               "y" | "z" ;
variable = (letter {digit | letter}) -keyword ;
operator = "<=" |">=" | "==" | "!=" | "&&" | "||" | "=" | "+" | "-" | "*" | "<" |  ">" | "!" ;
punctuation = "(" | ")" | " {" | " }" | " , " | " ; " ;

现在我想计算FIRST，FOLLOW和PREDICT集，但我不知道如何用EBNF表示法。我应该先把它换成乔姆斯基普通形式吗？那是怎么回事？那是对的吗？

DIGIT -> 0 1 2 3 ...
INT -> DIGIT | DIGIT DIGIT
BOOL -> true false 
KEYWORD -> if while BOOL
LETTER -> A B C D ...
VARIABLE -> LETTER | LETTER DIGIT | LETTER LETTER

Answer 1

首先，即使使用EBNF，也非常直截了当。在这种情况下，它们更容易，因为您没有可以为空的非终端。 （你需要注意重复组，因为重复次数可以是0.如果你有：

... A { X ... } Y ...

然后跟随（A）必须包括FIRST（X）和FIRST（Y）。如果你有

C -> A { X }

然后跟随（A）必须包括FOLLOW（C）。

如果您手动进行计算，这些都不应该是复杂的。对于自动化解决方案，我可能会通过创建新的非终端将重复运算符展开到未扩展的BNF中，但您也可以直接在EBNF上进行计算。

一个皱纹是你使用集差分算子-，in

variable = (letter {digit | letter}) - keyword ;

在这种特殊情况下，它不会产生任何困难，但一般的解决方案很棘手。实际上，由于无法保证两种无上下文语言之间的区别是无上下文的，因此找不到真正通用的解决方案是不可能的。

预测集是另一个故事。实际上，我甚至不能100％确定EBNF的预测集是什么，因为您需要能够预测子模式的重复，而不仅仅是推导。同样，扩展到BNF可能会有所帮助，但可能会发生扩展产生预测冲突，这种冲突在原始语法中不存在。

你提出的语法是不完整的，所以我不知道计算LL（1）集会有多大用处。我认为它只是语法的词汇部分，但实际上有一个理由是为什么词法分析通常使用正则表达式而不是无上下文解析。

实际上有几个原因：除了词法分析通常涉及合理可读的正则表达式这一事实外，还有一个重要的事实，即词法分析通常不涉及解析令牌的内部结构。这让你可以选择简单地识别一个重复的元素，而不是担心重复的解析树是左倾还是右倾。

计算FIRST和FOLLOW集的关键见解是它们的意思就是它们的名字所表示的内容。第一组非终端正是一组令牌，可以从非终端开始完全推导;类似地，FOLLOW集合恰好是在从起始符号推导期间可能紧跟非终端的令牌集合。在许多简单的语法中，这些集合可以通过检查来计算;这当然应该是你的语法的情况，至少对于第一组。

你这里没有起始符号的事实是另一个迹象表明你可能没有解决正确的问题;没有开始符号，没有有意义的FOLLOW定义。

如果您正在尝试进行词法分析，您可能会逃脱：

start -> { token }
token -> int literal | keyword | identifier | ...

虽然要正式更正，但您还需要处理“忽略的令牌”，例如注释和空格。