grammar - 用于识别语法产生正确性的标准算法

Question

我确信有一种标准的方法可以做到这一点，但我什至不知道从哪里开始搜索它。

我如何以任何语言识别结构（语法），例如：

Exp ::= Number |(Exp) | Exp + Exp 
Number ::= Number Digit | Digit
Digit ::= 0 | ... | 9

我的意思是，给定一个类似 的字符串32 + (43 + 23)，我如何判断它是否合法？有没有标准算法之类的？我不知道要搜索什么，所以我也无法搜索这个网站。

Answer 1

您正在寻找解析算法 (membership algorithim)。解析是分析形式语言中的一串语言符号的过程。是的，对于任何上下文无关的语法，都有一种可能的解析算法——Brute-Force 是一种基本算法，但效率低下，就像短语结构解析一样，它的最坏情况复杂度是 O(n ³ ) _{（你要从这里）} REFF1。但是如果语法是标准（受限）形式，那么更有效的算法是可能的。有各种解析算法，例如 LL 解析器和 LR 解析器..等。参考