compiler-construction - 类型 3 语法 - 正则表达式

Question

我读过一个说明，类型 3 语法不能同时拥有这两种产品

A-> aB
A-> Ba

其中 A,B 是非终结符，a 是终结符

我对类型 3 了解得够多了，但我无法理解上述内容

Answer 1

如果您允许这两种产生式发生，这将改变类型 3 的含义。您可以编写如下语法：

A -> '(' B
B -> A ')'
A -> '1'

如果你假设 A 是开始非终端，你的语言会给你所有的话

((...((1))...))

其中两边括号的数量相同。然而，这不是类型 3 语言（非正式地，正确的解析器需要计数，因此它不能是有限状态）。