檢查的字符串是形式0^N 1^N

Question

的我有一個Yacc的程序來檢查號碼的形式爲0^N 1^N。

%start S 
%% 
    S:'0' S '1' {printf("Success\n");}|; 
%% 

（所有令牌在法文件中定義）

我得到的輸出如下

0011 
Success 
Success 
syntax error 

1100 
syntax error 

我明白爲什麼成功打印了兩次，但什麼是語法錯誤做在第一個輸出？

此外，如何bison，一個LALR（1）語法分析器發電機做這個任務？

Answer 1

語法錯誤來自您的語法無法識別空字符串的事實，因此一旦所有的'1' S '0'產品都減少了，就無法取得進展。

野牛拒絕接受語法，但它是很容易解決：

%start S 
%% 
S: '1' S '0' 
| ; 
%% 

只看語法，應該很清楚如何分析一個令牌前瞻的字符串。實際上，語法是LL（1）;您只需要遇到的一個堆棧（或計數器）1。如果這不是一個足夠的解釋，啓用野牛的追蹤功能，並觀察解析發生。

Answer 2

的問題是，你的語法只匹配字符串無限 - 有在你的語法描述的語言中沒有有限串。

您需要添加一個「基本情況」用有限的字符串，所以它可以接受從它建立的是一個或多個字符串。明顯的情況是空字符串（對於n = 0）：

S : /* empty */ 
    | '0' S '1' 
    ;