识别语法生产正确性的标准算法

Question

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

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

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

我的意思是，鉴于32 + (43 + 23)这样的字符串，我该如何确定它是否合法？是否有标准算法或其他内容？我不知道要搜索什么，所以我无法搜索此网站。

Answer 1

您正在寻找解析算法（成员资格algorithim）。解析是分析形式语言中的一系列语言符号的过程。对于任何无上下文的格拉玛，是的，可能的解析算法是 brute-force a Brute-force a基本算法，但效率低下的，如短语结构解析，它的最差 - 案例复杂度为O（N ³ ）_{（您要从此处开始）} reff1 。但是，如果语法为标准（受限）形式，则可以更有效的算法。有各种解析算法，例如LL解析器和LR Parser..Etc。 reffrence