algorithm - Is there an algorithm for determining if given sentence is a sub-sentence of a grammar?

Question

For example, given the grammar

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

we see that for + 1 there exists a sentence (e.g. 1 + 1) which is parsed by the grammar and for which + 1 is sub-sentence. Is there a general algorithm for this? I think that if we can put some kind of flags in the parser we should be able to tell it to skip some initial and some final tokens while parsing but I'm not sure whether this would work. Any ideas?

Answer 1

我确信有更好的方法，但这个论点表明，上下文无关语言类在此操作下通过乔姆斯基范式语法的线性时间转换关闭。

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

对于转换 A -> s，添加

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

对于转换 A -> BC，添加

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

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