这种语言可以用非二义性 BNF 语法来描述吗？

Question

在离开这个话题 20 多年（自从我获得 CS 本科学位以来）之后，我又回到了语言设计/规范（通过 BNF/EBNF 语法）。

我只是模糊地记得这个领域的各种相关术语，比如 LR(1)、LALR 等。我一直在尝试通过一些谷歌搜索和阅读来刷新，但它来得很慢（可能是因为我没有完全理解这些东西回到学校）。所以我可能做事相当粗略。

我决定用语法来描述一种玩具语言，然后尝试分析并可能优化它，作为我重新学习的一部分。

注意：下面的所有片段也可以在此处的要点中找到。

我从 EBNF 表示开始（由该工具处理/验证）：

Program                 := WhSp* (StmtSemi WhSp*)* StmtSemiOpt? WhSp*;
Stmt                    := AStmt | BStmt | CStmt | DStmt;
StmtSemi                := Stmt? (WhSp* ";")+;
StmtSemiOpt             := Stmt? (WhSp* ";")*;
WhSp                    := "_";
AStmt                   := "a";
BStmt                   := "b";
CStmt                   := "c";
DStmt                   := "d";

以下是该语言的一些有效匹配（每行一个匹配）：

_____
;;;;;
_;_;_
a
__a__
a;
a;b;
a;_b;
_a;_b;_
_a_;_b_;_
__a__;;
_;_a;_b;c;;;__;;__d;___a___

这里有一些该语言中没有的值（同样，每行一个）：

ab
a_b
a;_b_c

然后我将其手动转换为以下 BNF 形式（由该工具处理/分析）：

Program                 -> StmtSemi FinalStmtSemiOpt .
StmtSemi                -> WhSp StmtSemiOpt | StmtSemiOpt .
FinalStmtSemiOpt        -> StmtOpt SemiOpt WhSpOpt | WhSpOpt .

Stmt                    -> AStmt | BStmt | CStmt | DStmt .
StmtOpt                 -> Stmt | .
StmtSemiOpt             -> StmtOpt Semi | StmtOpt Semi WhSpOpt StmtSemiOpt | .

Semi                    -> WhSpOpt ; | WhSpOpt ; Semi .
SemiOpt                 -> Semi | .

WhSp                    -> _ | _ WhSp .
WhSpOpt                 -> WhSp | .

AStmt                   -> a .
BStmt                   -> b .
CStmt                   -> c .
DStmt                   -> d .

该工具的分析表明我的语法不明确。我想这并不奇怪，也不一定是一个糟糕的结果，但我知道不明确的语法限制了某些类型的分析和自动转换或解析器生成。

所以...最后，这是我的问题：

1. 这是上下文无关语法吗？到底是什么让它如此，或者使它成为非 CFG？

   [编辑：“是”，请参阅@rici的回答]

2. 我所描述的语言可以用明确的语法（BNF 或 EBNF）来指定吗？或者它本身就是模棱两可的？

3. 如果它本质上是不明确的，那么该语言的哪些具体方面使它如此？换句话说，为了获得一种具有明确语法的语言，我至少需要更改/删除什么？

4. 是否有有意义的方法可以简化我的 BNF 语法形式并仍然描述与 EBNF 相同的语言？

5. BNF 语法目前有左递归、右递归还是两者都有？我很难说服自己相信答案。是否可以重新安排 BNF 以避免其中之一，这会产生什么影响（性能等）？

   [编辑：根据分析工具，我相信更新后的 BNF 只有右递归。]

如果我摸索着不正确的术语或提出不精确的问题，请道歉。感谢您提供的任何见解。

---

[编辑：这是一个新的 BNF，我认为它是等效的，但并不含糊——感谢 @rici 确认它是可能的。我没有为此使用任何特定的算法/策略，只是不断尝试错误。]

Leading                 -> WhSp Leading Program | Semi Leading Program | Program .
Program                 -> Stmt | Stmt WhSp | Stmt WhSpOptSemi Program | Stmt WhSpOptSemi WhSp Program | .

Stmt                    -> AStmt | BStmt | CStmt | DStmt .

WhSpOptSemi             -> Semi | WhSp Semi | Semi WhSpOptSemi | WhSp Semi WhSpOptSemi .
WhSp                    -> _ | _ WhSp .
Semi                    -> ; .

AStmt                   -> a .
BStmt                   -> b .
CStmt                   -> c .
DStmt                   -> d .

我猜这似乎回答了问题（2）、（3）和部分（4）。

Answer 1

证明语法是二义性的并不总是容易的（甚至是可能的），但是如果有一个简短的二义性句子，那么可以通过暴力枚举找到它，这就是我相信该工具所做的。输出是有启发性的；最短的歧义句是空串。

因此，剩下的只是弄清楚为什么空字符串可以用两种（或更多）方式解析，并且快速查看产生式会发现它FinalStmtSemiOpt有两个可为空的产生式，这意味着它有两种派生空字符串的方法。如果您相信名称以 结尾的每个产生式Opt实际上描述了一个可选序列，那么通过检查就可以看出这一点，因为FinalStmtSemiOpt有两个产生式，每个产生式仅由XOpts 组成。需要付出更多的努力来验证可选的非终结符实际上是可选的，这是应该的。

因此，解决方案是重新设计FinalStmtSemiOpt而不使用两个可为空的右侧。那应该不会太难。

您提出的几乎所有其他问题都可以通过检查来回答：

• 语法是上下文无关的（根据定义）当且仅当每个产生式的左侧都恰好有一个符号。（如果它有多个符号，那么额外的符号定义了一个上下文，在该上下文中替换是有效的。如果没有产生式具有上下文，则该语法是上下文无关的。）

• 如果非终结符的某些产生式以非终结符本身开始（直接左递归），或者以一系列可空非终结符开始，后跟非终结符本身（间接），则非终结符是左递归的左递归）。换句话说，非终结符是或可能是产生式中最左边的符号。类似地，如果某些产生式以非终结符结束（同样，可能后面跟着可为空的非终结符），则非终结符是右递归的。

• 没有任何算法可以一般地告诉您一种语言是否本质上是二义性的，但在特定情况下，一种语言是规则的，那么它绝对不是本质上二义性的。具有正则语法的语言是正则的，但非正则语法仍然可以描述正则语言。你的语法不规则，但无需太多工作（主要是重构）即可使其规则。暗示它可能是常规的，因为没有递归嵌套语法（例如括号或语句块）。大多数有用的语法都是递归嵌套的，并且嵌套绝不意味着歧义。所以这不会让你走得太远，但这里恰好就是这种情况。