我正在学习计算语言测试,有一个想法我无法理解。
我知道常规语法更简单并且不能包含歧义,但无法完成编程语言所需的许多任务。我还了解到,上下文无关语法允许歧义,但允许编程语言必需的一些东西(例如回文)。
我遇到的困难是理解如何通过知道常规语法非终结符可以映射到一个终结符或一个非终结符后跟一个终结符或上下文来导出上述所有内容免费非终结符映射到终结符和非终结符的任意组合。
有人可以帮我把所有这些放在一起吗?
最佳答案
常规语法是右线性或左线性的,而上下文无关语法基本上是终结符和非终结符的任意组合。因此,您可以看到常规语法是上下文无关语法的子集。
例如,对于回文,其形式为,
S->ABA
A->something
B->something
您可以清楚地看到回文不能用常规语法表达,因为它需要是右线性或左线性的,因此两侧不能有非终结符。
由于常规语法是非二义性的,因此对于给定的非终结符只有一个产生规则,而在上下文无关语法的情况下可以有多个规则。
关于context-free-grammar - 常规语法与上下文无关语法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/559763/