为什么 C++ 不能用 LR(1) 解析器解析？

StackOverflow https://stackoverflow.com/questions/243383

题

我正在阅读有关解析器和解析器生成器的内容，并在维基百科的 LR 解析页面中找到了此声明：

许多编程语言都可以使用 LR 解析器的某些变体进行解析。一个值得注意的例外是 C++。

为什么会这样呢？C++ 的什么特殊属性导致它无法用 LR 解析器进行解析？

使用google，我只发现C可以用LR(1)完美解析，但C++需要LR(∞)。

有帮助吗？

解决方案

Lambda the Ultimate 上有一个有趣的主题，讨论 C ++的LALR语法。

它包含指向博士论文的链接其中包括对C ++解析的讨论，其中指出：

  

<！>“C ++语法含糊不清，   依赖于上下文和潜在的   需要无限的前瞻来解决   一些歧义<！>“。

接着提供了一些例子（参见pdf的第147页）。

示例是：

int(x), y, *const z;

含义

int x;
int y;
int *const z;

比较：

int(x), y, new int;

含义

(int(x)), (y), (new int));

（以逗号分隔的表达式）。

两个令牌序列具有相同的初始子序列但具有不同的解析树，这取决于最后一个元素。在消除歧义之前，可以有任意多个令牌。

其他提示

LR解析器无法通过设计处理模糊的语法规则。 （在20世纪70年代制定这些想法时，理论变得更容易了。）

C和C ++都允许以下语句：

x * y ;

它有两种不同的解析：

  1. 它可以是y的声明，作为指向x
    2. 的指针
  2. 它可以是x和y的乘法，丢掉了答案。

    3. 现在，您可能认为后者是愚蠢的，应该被忽略。 大多数人会同意你的意见;但是，有些情况可能会发生 有副作用（例如，如果乘法过载）。但这不是重点。 关键是是两个不同的解析，因此是一个程序 可能意味着不同的东西取决于应该如何解析。

    编译器必须在适当的情况下接受适当的信息，并且在没有任何其他信息（例如，x的类型的知识）的情况下必须收集两者以便稍后决定做什么。因此语法必须允许这样。这使得语法含糊不清。

    因此纯LR解析无法处理此问题。许多其他广泛可用的解析器生成器，例如Antlr，JavaCC，YACC或传统Bison，甚至PEG样式解析器，也不能用于<！>“pure <！>”;方式。

    有许多更复杂的情况（解析模板语法需要任意前瞻，而LALR（k）可以向前看大多数k代币），但只有一个反例才能击落纯 LR（或其他）解析。

    大多数真正的C / C ++解析器通过使用一些来处理这个例子 一种具有额外黑客攻击的确定性解析器：它们与符号表交织解析 集合...所以到时间<！>“x <！>”;遇到了， 解析器知道x是否是类型，因此可以 在两个潜在的解析之间做出选择。但解析器 这不是上下文，LR解析器 （纯粹的等等）（最好）没有上下文。

    可以作弊，并添加每个规则缩减时间语义检查 到LR解析器做消除歧义。 （这段代码通常不简单）。大多数其他解析器类型 有一些方法可以在各个点添加语义检查 在解析中，可以用来做到这一点。

    如果你作弊足够，你可以让LR解析器工作 C和C ++。海湾合作委员会的人做了一段时间，但给了它 手动编码解析，我认为因为他们想要 更好的错误诊断。

    然而，还有另一种方法，它既干净又干净 并且在没有任何符号表的情况下解析C和C ++就好了 hackery： GLR解析器。 这些是完全无上下文解析器（实际上是无限的 展望）。 GLR解析器只接受两个解析， 产生<！>“树<！>”; （实际上是一个主要是树状的有向无环图） 这代表了模棱两可的解析。 解析后的传递可以解决歧义。

    我们在C和C ++前端使用这种技术 DMS Software Reengineering Tookit（截至2017年6月 这些处理MS和GNU方言中的完整C ++ 17）。 它们已被用于处理数百万行 大型C和C ++系统，具有完整，精确的解析，生成具有完整源代码细节的AST。 （请参阅 AST for C ++最令人烦恼的解析。）

问题从来没有像这样定义过，但它应该很有趣：

为了让“非上下文无关”yacc 解析器可以完美地解析这个新语法，对 C++ 语法进行的最小修改集是什么？（仅使用一种“黑客”：类型名/标识符消歧，解析器通知词法分析器每个 typedef/类/结构）

我看到有几个：

  1. Type Type; 是禁止的。声明为类型名的标识符不能成为非类型名标识符（请注意 struct Type Type 是明确的，并且仍然可以被允许）。

    有3种类型 names tokens :

    • types ：内置类型或由于 typedef/class/struct
    • 模板函数
    • 身份标识 ：函数/方法和变量/对象

    将模板函数视为不同的标记解决了 func< 含糊不清。如果 func 是模板函数名称，那么 < 必须是模板参数列表的开头，否则 func 是一个函数指针并且 < 是比较运算符。

  2. Type a(2); 是一个对象实例化。Type a(); 和 Type a(int) 是函数原型。

  3. int (k); 是完全禁止的，应该写成 int k;

  4. typedef int func_type(); 和typedef int (func_type)(); 被禁止。

    函数 typedef 必须是函数指针 typedef ： typedef int (*func_ptr_type)();

  5. 模板递归限制为 1024，否则可以将增加的最大值作为选项传递给编译器。

  6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); 也可以被禁止，替换为 int a,b,c[9],*d; int (*f)();

    int (*g)()[9];

    int h(char);

    每个函数原型或函数指针声明一行。

    一个高度首选的替代方案是更改可怕的函数指针语法，

    int (MyClass::*MethodPtr)(char*);

    被重新语法为：

    int (MyClass::*)(char*) MethodPtr;

    这与强制转换运算符一致 (int (MyClass::*)(char*))

  7. typedef int type, *type_ptr; 也可能被禁止：每个 typedef 一行。这样就变成了

    typedef int type;

    typedef int *type_ptr;

  8. sizeof int, sizeof char, sizeof long long 和公司。可以在每个源文件中声明。因此，每个源文件都使用类型 int 应该开始于

    #type int : signed_integer(4)

    和 unsigned_integer(4) 除此之外将被禁止 #type 指令这将是迈向愚蠢的一大步 sizeof int 许多 C++ 头文件中存在歧义

如果遇到使用不明确语法的 C++ 源代码，实现重新语法的 C++ 的编译器将移动 source.cpp 太安 ambiguous_syntax 文件夹，并会自动创建一个明确的翻译 source.cpp 在编译之前。

如果您知道一些不明确的 C++ 语法，请添加！

正如您在我的在此处回答，C ++包含LL或LR解析器无法确定性解析的语法，因为类型解析阶段（通常是解析后）更改操作顺序，因此基本形状AST（通常预期由第一阶段解析提供）。

我认为你非常接近答案。

LR（1）意味着从左到右的解析只需要一个令牌来预测上下文，而LR（<！>＃8734;）意味着无限前瞻。也就是说，解析器必须知道即将发生的所有事情，以便找出它现在的位置。

<！> quot; typedef <！> quot; C ++中的问题可以使用LALR（1）解析器进行解析，该解析器在解析时构建符号表（不是纯LALR解析器）。 <！>“模板<！>”;用这种方法可能无法解决问题。这种LALR（1）解析器的优点是语法（如下所示）是LALR（1）语法（没有歧义）。 

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

可以毫无问题地解析以下输入：

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

LRSTAR解析器生成器读取上述语法表示法并生成一个解析器，用于处理<！> quot; typedef < ！> QUOT;在解析树或AST中没有歧义的问题。 （披露：我是创建LRSTAR的人。）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top