YACC和上下文無關文法

Question

我無法爲以下問題派生yacc程序。

對於具有的相等數目的字符串和b的是如下

S上的語法 - >一個S B S | b S a S | epsilon

我想知道是否有可能爲它製作YACC程序。在編寫代碼的同時，我意識到如果輸入不具有相同的a和b。我應該在YACC打印一些表明字符串無效的消息？

Answer 1

yacc爲LALR(1)語法實現解析器;語法（和，我相信，語言）不是LALR(1)。 （這與我下面的第一點有關。）

如果您使用bison（很可能），那麼您可以使用%glr選項生成GLR語法，在這種情況下，該語法的天真音譯將起作用。但是，你會遇到兩個問題：

1. 最有效字符串有多個解析和野牛的GLR分析器堅持認爲，最終的結果不會含糊。我不知道是否有一個簡單的解決這個使用%dprec，但其可能的。

2. 你不能告訴，直到你到達字符串結尾的字符串不符合語法，因爲任何字符串是一個有效的字符串的前綴。 （你只需要添加少數符號足以實現平等。）