0

我很难弄清楚这个问题以及轮班减少问题。

添加';' 到最后并没有解决问题，因为我不能改变语言，它需要像下面的例子一样。任何 prec 操作数都有效吗？

示例如下：

变量可以声明为：作为指针或 int 作为整数，因此，这两者都是有效的：

<int> a = 0
int a = 1

代码如下：

%left '<'

declaration: variable
           | declaration variable

variable : type tNAME '=' expr
         | type tNAME

type : '<' type '>'
     | tINT

expr : tINTEGER
     | expr '<' expr

它显然在 expr 之后给出了移位/减少问题。因为它可以转换为“less”运算符的 expr 或减少另一个变量声明。

我希望优先考虑变量声明，并尝试创建一个 %nonassoc prec_aux 并放在 '<' type '>' %prec prec_aux 和 type tNAME 之后，但这并不能解决我的问题：S

我该如何解决这个问题？

输出是：

好吧，我不知道如何在回复时发布换行符和代码......所以这里是输出：

35: shift/reduce conflict (shift 47, reduce 7) on '<'
state 35
    variable : type tNAME '=' expr .  (7)
    expr : expr . '+' expr  (26)
    expr : expr . '-' expr  (27)
    expr : expr . '*' expr  (28)
    expr : expr . '/' expr  (29)
    expr : expr . '%' expr  (30)
    expr : expr . '<' expr  (31)
    expr : expr . '>' expr  (32)

    '>'  shift 46
    '<'  shift 47
    '+'  shift 48
    '-'  shift 49
    '*'  shift 50
    '/'  shift 51
    '%'  shift 52
    $end  reduce 7
    tINT  reduce 7

这就是输出，错误似乎是我提到的那个。

有没有人知道一个不同的解决方案，除了添加一个新的终端到语言中，这不是一个真正的选择？

我认为解决方案是重写语法，以便它可以以某种方式向前看，看看它是在“​​<”之后的类型还是 expr，但我不知道如何去做。

优先级不太可能起作用，因为它具有相同的特征。有没有办法让我们定义的类型优先？比如声明？

提前致谢

4

3 回答 3

2

您的语法在这样的文本中变得混乱：

int a = b
<int> c

第二行的“<”可能是第一个声明中表达式的一部分。它必须进一步向前看才能找到答案。

这就是大多数语言都有语句终止符的原因。这不会产生冲突：

%%

%token tNAME;
%token tINT;
%token tINTEGER;
%token tTERM;

%left '<';

declaration: variable
           | declaration variable

variable : type tNAME '=' expr tTERM
         | type tNAME tTERM

type : '<' type '>'
     | tINT

expr : tINTEGER
     | expr '<' expr

在创建解析器时了解如何设计语法以消除可能的冲突会有所帮助。为此，您需要了解解析器的工作原理，这超出了此答案的范围:)

于 2012-04-16T19:05:43.740 回答
1

这里的基本问题是您需要比使用 yacc/bison 获得的 1 个令牌更多的前瞻。当解析器看到 a<时，它无法判断它是否完成了先前的声明以及它是否正在查看括号类型的开头，或者这是否是一个小于运算符。您可以在这里做两件基本的事情：

  • 使用 bison 的%glr-parseroption 或btyacc等解析方法，可以处理非 LR(1) 语法

  • 使用词法分析器进行额外的前瞻并返回消除歧义的标记

对于后者，您可以让词法分析器在 '<' 之后进行额外的前瞻，如果它后面跟着一个看起来像类型的东西，则返回一个不同的标记。最简单的是使用 flex 的/前瞻操作符。例如：

"<"/[ \t\n\r]*"<"    return OPEN_ANGLE;
"<"/[ \t\n\r]*"int"  return OPEN_ANGLE;
"<"                  return '<';

然后你改变你的野牛规则以期望OPEN_ANGLE类型而不是<：

type : OPEN_ANGLE type '>'
     | tINT

expr : tINTEGER
     | expr '<' expr

对于更复杂的问题，您可以使用弹性启动状态，甚至在词法分析器和解析器之间插入整个令牌过滤器/转换通道。

于 2012-04-17T22:48:01.203 回答
0

这是修复，但并不完全令人满意：

%{
%}

%token tNAME tINT tINTEGER

%left '<'
%left '+'
%nonassoc '=' /* <-- LOOK */

%%

declaration: variable
           | declaration variable

variable : type tNAME '=' expr
         | type tNAME

type : '<' type '>'
     | tINT

expr : tINTEGER
     | expr '<' expr
     | expr '+' expr
     ;

这个问题是这两个 LR 项目之间的冲突：dot-final：

variable : type tNAME '=' expr_no_less .

和这个：

expr : expr . '<' expr

请注意，这两个具有不同的运算符。正如您似乎认为的那样，这不是涉及“<”运算符的不同产品之间的冲突。

通过添加=优先级排名，我们解决了冲突诊断消失的问题。

请注意，我给予=了很高的优先级。这将通过支持减少来解决冲突。这意味着您不能使用 '<' 表达式作为初始值设定项：

int name = 4 < 3    // syntax error

当看到 < 时，int name = 4想要减少，并且想法是它<必须是下一个声明的开始，作为type生产的一部分。

要允许将<关系表达式用作初始值设定项，请将对括号的支持添加到表达式语法中。然后用户可以用括号括起来：

int foo = (4 < 3) <int> bar = (2 < 1)

如果没有更强大的解析方法或黑客，就无法解决这个问题。

如果你移动%nonassocbefore %left '<'，给它低优先级怎么办？那么这种转变将受到青睐。不幸的是，这会导致您无法<int>在声明之后编写另一个声明。

int foo = 3 <int> bar = 4
             ^ // error: the machine shifted and is now doing:   expr '<' . expr.

所以这是解决冲突的错误方法；您希望能够编写多个这样的声明。

另一个注意事项：

我的 TXR 语言实现了类似于 Parse Expression Grammars 的功能，可以很好地处理这种语法。这本质上是 LL（无限），它胜过 LALR（1）。

我们甚至不需要单独的词法分析器和解析器！这只是一个符号前瞻的限制以及对 1970 年硬件的最大效率的需要所必需的。

来自 shell 命令行的示例输出，演示了通过转换为类似于 Lisp 的抽象语法树进行的解析，该语法树绑定到变量dl（声明列表）。所以这与语义动作一起完成，产生可以在 TXR Lisp 中进一步处理的输出。标识符通过调用转换为 Lisp 符号intern，数字也被转换为数字对象。

$ txr -l type.txr  -
int x = 3 < 4 int y
(dl (decl x int (< 3 4)) (decl y int nil))

$ txr -l type.txr  -
< int > x = 3 < 4 < int > y
(dl (decl x (pointer int) (< 3 4)) (decl y (pointer int) nil))

$ txr -l type.txr  -
int x = 3 + 4 < 9 < int > y < int > z = 4 + 3 int w
(dl (decl x int (+ 3 (< 4 9))) (decl y (pointer int) nil) 
 (decl z (pointer int) (+ 4 3)) (decl w int nil))

$ txr -l type.txr  -
<<<int>>>x=42  
(dl (decl x (pointer (pointer (pointer int))) 42))

( ) 的源代码type.txr：

@(define ws)@/[ \t]*/@(end)
@(define int)@(ws)int@(ws)@(end)
@(define num (n))@(ws)@{n /[0-9]+/}@(ws)@(filter :tonumber n)@(end)
@(define id (id))@\
   @(ws)@{id /[A-Za-z_][A-Za-z_0-9]*/}@(ws)@\
   @(set id @(intern id))@\
@(end)
@(define type (ty))@\
  @(local l)@\
  @(cases)@\
    @(int)@\
    @(bind ty @(progn 'int))@\
  @(or)@\
    <@(type l)>@\
    @(bind ty @(progn '(pointer ,l)))@\
  @(end)@\
@(end)
@(define expr (e))@\
  @(local e1 op e2)@\
  @(cases)@\
    @(additive e1)@{op /[<>]/}@(expr e2)@\
    @(bind e @(progn '(,(intern op) ,e1 ,e2)))@\
  @(or)@\
    @(additive e)@\
  @(end)@\
@(end)
@(define additive (e))@\
  @(local e1 op e2)@\
  @(cases)@\
    @(num e1)@{op /[+\-]/}@(expr e2)@\
    @(bind e @(progn '(,(intern op) ,e1 ,e2)))@\
  @(or)@\
    @(num e)@\
  @(end)@\
@(end)
@(define decl (d))@\
  @(local type id expr)@\
  @(type type)@(id id)@\
  @(maybe)=@(expr expr)@(or)@(bind expr nil)@(end)@\
  @(bind d @(progn '(decl ,id ,type ,expr)))@\
@(end)
@(define decls (dl))@\
  @(coll :gap 0)@(decl dl)@(end)@\
@(end)
@(freeform)
@(decls dl)
于 2012-04-17T21:52:11.800 回答