algorithm - 是否有一种算法可以确定给定的句子是否是语法的子句？

Question

例如，给定语法

Expr -> Number | Number '+' Expr
Number -> [1-9][0-9]*

我们看到对于 + 1 存在一个句子(例如 1 + 1)，它被语法解析为 + 1 是子句。有没有通用的算法？我认为如果我们可以在解析器中放置某种标志，我们应该能够告诉它在解析时跳过一些初始和一些最终标记，但我不确定这是否可行。有什么想法吗？

Answer 1

我确信有更好的方法，但这个论证表明上下文无关语言类在这个操作下通过 Chomsky 范式语法的线性时间转换是封闭的。

想法是为每个非终结符号 A 引入另外三个符号 Apre、Asuf、Asub，它们匹配 A 匹配的字符串的前缀、后缀和子串。

对于转换 A -> s，添加

Apre ->
Apre -> s
Asuf ->
Asuf -> s
Asub ->
Asub -> s.

对于转换 A -> B C，添加

Apre -> Bpre
Apre -> B Cpre
Asuf -> Csuf
Asuf -> Bsuf C
Asub -> Bsub
Asub -> Csub
Asub -> Bsuf Cpre.

将起始符号从 S 更改为 Ssub。