grammar - 这种上下文无关的语法是明确的吗？

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 是产生式集合。

标签： grammartheorycontext-free-grammar

Answer 1

这种语法是明确的，也是不确定的。当对于至少一个有效的输入字符串存在多于一个语法树时，语法是不明确的，并且是确定性的，如果对于每个有效的输入字符串，在解析期间的任何时间，都只有一个要使用的预测。对于无效的输入字符串，会有一段时间没有预测可以使用。

预测M → S + S，M → S - S并使M → S语法具有不确定性，因为S是它们每个的第一个非终结符号。但是，在解析所有输入之后，这不会导致任何输入的多于一个语法树，因为Sare +、-(in M) 和非终结符in)之后的终结符号将一致地确定哪个预测是有效的。MS → ( 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] ")"