我怎样才能迫使野牛转向解决冲突? [英] How can I force Bison to shift to resolve a conflict?

问题描述

我正在为一种简单的编程语言构建此语法(已经解决了以前的歧义问题:).

这是我完整的语法: http://pastebin.com/yBHLSP0z
这是Bison的输出文件: http://pastebin.com/eAma3gWy
(对不起，它们是西班牙语，但我认为它们非常不言而喻)

问题是，在状态107(我正在翻译)时，我仍然遇到一个移位/减少错误:

I'm building this grammar for a simple programming language (already solved previous ambiguity issues: Can't figure out why Bison is throwing "Rules useless in parser due to conflicts").

This is my complete grammar: http://pastebin.com/yBHLSP0z
And this is the output file from Bison: http://pastebin.com/eAma3gWy
(sorry, they're in Spanish, but I think they're pretty self-explanatory)

The thing is, I'm still getting one shift/reduce error at state 107 (I'm translating it):

state 107

31 factor: ID .
48 concatenacion: ID . OPERADOR_SUMA ID
49              | ID . OPERADOR_SUMA literal_string

OPERADOR_SUMA  shift and go to state 140
OPERADOR_SUMA  [reduce using rule 31 (factor)]
$default       reduce using rule 31 (factor)

现在，从状态70调用状态107:

Now, state 107 is called from state 70:

estado 70

   45 asignacion: ID OPERADOR_ASIGNACION . concatenacion
   46           | ID OPERADOR_ASIGNACION . expresion
   47           | ID OPERADOR_ASIGNACION . literal_string

    OPERADOR_RESTA   desplazar e ir al estado 55
    PARENTESIS_ABRE  desplazar e ir al estado 56
    COMILLA          desplazar e ir al estado 67
    ID               desplazar e ir al estado 107

    expresion       ir al estado 108
    termino         ir al estado 61
    factor          ir al estado 62
    concatenacion   ir al estado 109
    literal_string  ir al estado 110
    literal_real    ir al estado 63
    literal_entero  ir al estado 64
    signo           ir al estado 65

我认为正在发生的事情(如果我错了，请纠正我)是当它找到这样的指定"规则时:

What I think is happening (please correct me if I'm wrong) is that when it finds a rule for "asignacion" like this:

asignacion: ID OPERADOR_ASIGNACION concatenacion | ID OPERADOR_ASIGNACION expresion

它发现从表达式"中可以获取一个ID令牌(表达式> termino>因子> ID)，从而生成一个 ID OPERADOR_ASIGNACION ID :

it sees that from "expresion" it can get an ID token (expresion > termino > factor > ID), making a ID OPERADOR_ASIGNACION ID:

expresion:  
        expresion OPERADOR_SUMA termino
        | expresion OPERADOR_RESTA termino
        | termino
        ;


termino:
        termino OPERADOR_MULTIPLICACION factor
        | termino OPERADOR_DIVISION factor
        | factor
        ;


factor:     
        ID
        | literal_entero
        | literal_real
        | PARENTESIS_ABRE expresion PARENTESIS_CIERRA
        ;

现在，当它到达 ID OPERADOR_ASIGNACION链接并查看"concatenacion"的规则时，它将得到:

Now, when it reaches an ID OPERADOR_ASIGNACION concatenacion and looks at the rules for "concatenacion", it gets:

concatenacion:
        ID OPERADOR_SUMA ID 
        | ID OPERADOR_SUMA literal_string 
        | literal_string OPERADOR_SUMA ID 
        | literal_string OPERADOR_SUMA literal_string
        ;

其中两个以"ID"开头.因此，如果选择了这两个规则中的任何一个，它将进入一个状态，可以获取 ID OPERADOR_ASIGNACION ID ，只有使用"concatenacion"规则，它之后才需要找到"OPERADOR_SUMA"令牌.但是我相信，一旦从"concatenacion"和"expresion"中都可以形成 ID OPERADOR_ASIGNACION ID 表达式，这将是令人窒息的.
如果这不是正在发生的事情，那么我想知道问题出在哪里.
而且，如果我对错误发生的位置是正确的，那么我真的不知道如何解决.
请帮助:)

谢谢！

Two of them begin with "ID". So if any of those two rules are selected, it gets to a state where it can obtain a ID OPERADOR_ASIGNACION ID, only that with the "concatenacion" rules, it needs to find a "OPERADOR_SUMA" token afterwards. But I believe it's choking as soon as it sees that from both "concatenacion" and "expresion" can form the ID OPERADOR_ASIGNACION ID expression.
If this is not exactly what's going on, I'd like to know what is then the problem.
And, if I'm correct as where the error happens, I really don't know how to solve it.
Please help :)

Thanks!

推荐答案

问题来自于:

asignacion
    :   ID OPERADOR_ASIGNACION concatenacion
    |   ID OPERADOR_ASIGNACION expresion
    ;

和所选的替代项:

expresion
    :   expresion OPERADOR_SUMA termino
    ;

termino
    :   factor
    ;

factor
    :   ID
    ;

concatenacion
    :   ID OPERADOR_SUMA ID
    ;

这意味着您的解析器遇到以下情况:

Which means that when your parser encounters:

x = y + z

它无法确定它是否正在处理asignacion的第一种或第二种选择.

it cannot tell whether it is processing the first or second alternative for asignacion.

那是容易的部分.怎么修?最简单的解决方法(如果可行，我尚未测试过)将删除我显示的concatenacion规则，并在expresion规则中，识别您在处理concatenacion与expresion时的区别.因为它们在语法上是相同的:

That's the easy part. How to fix? The simplest fix (if it works, which I've not tested) would be to remove the concatenacion rule I showed, and in the expresion rule, recognize when you are dealing with a concatenacion vs an expresion since they are syntactically identical:

ID OPERADOR_SIGNACION ID OPERADOR_SUM ID

您将查看expresion的两个操作数的类型，如果它们都是字符串类型，则假定它是concatenacion，否则为expresion.

You'd look at the types of the two operands of the expresion, and if they are both string types, then you'd assume it was a concatenacion, otherwise an expresion.

不过，您可能希望查看整个concatenacion规则.我想，您需要让字符串通过factor规则，因此您需要为factor添加另一种替代方法:

You might want to review the whole of the concatenacion rule, though. You'd need to let strings through the factor rule, I think, so you'd add another alternative to factor:

factor
   :   literal_string
   ;

这意味着您将不得不拒绝其他规则中的文字字符串，因此需要进行更多的语义检查.一种替代方法是引入+以外的单独运算符来表示字符串连接". SQL使用||;某些语言使用了,；您可以一起使用另一个令牌，例如@.一旦脱离+，就有许多选择.您甚至可以只使用两个相邻的字符串表达式意味着连接操作"，而在它们之间没有任何运算符吗?

It would mean you'd have to reject literal strings in other rules, though, so more semantic checking. An alternative is to introduce a separate operator other than + to mean 'string concatenation'. SQL uses ||; some languages have used ,; you could use another token altogether, such as @. There are many options once you break away from +. Can you even just use 'two adjacent string expressions mean the concatenation operation', with no operator between them?

如果这些都不起作用，请回到我身边.

If none of that works, then get back to me.

这篇关于我怎样才能迫使野牛转向解决冲突?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！