这个上下文无关文法是否明确？

Question

我想知道我想出的语法是否没有歧义。

G(N, T, P, S)

N = {S, M}
T = {+, -, (, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
P = {
S → 0, S → 1, … , S → 9
S → ( M )
M → S + S
M → S - S
M → S
}

S 是起始变量，N 是非终结符集，T 是终结符集，P 是产生式集。

Answer 1

这个文法是明确的，也是不确定的。当存在多于一棵语法树时，语法是不明确的，至少一个有效输入字符串，并且是确定性的，如果每个有效输入字符串，在解析过程中的任何时候，只有一个预测可以使用。对于无效的输入字符串，有时会使用 none 个预测。

预测 M → S + S、M → S - S 和 M → S 使文法不确定，因为 S 是它们每个的第一个非终结符号。但是，在解析所有输入后，这不会导致任何输入的语法树超过一棵，因为 S 之后的终端符号是 +、-（在 M) 和 ) 在 S → ( M ) 中的非终结符 M 之后将一致确定哪个预测有效。

这个语法可以用 ABNF 标准语法写成这样：

S = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" / "(" M ")"
M = S "+" S / S "-" S / S

左重构后，语法可以变成确定性语法（不会改变歧义，即语法仍然是无歧义的）：

S = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" / "(" M ")"
M = S [("+" / "-") S]

并且使用更短的 ABNF 范围语法：

S = %x30-39 / "(" M ")"
M = S [("+" / "-") S]

或者使用单行本，其下有自动机：

S = %x30-39 / "(" S [("+" / "-") S] ")"

这个上下文无关文法是否明确？

Is this context-free grammar unambiguous?

theory

grammar

context-free-grammar