1. 使用 flex 和 Bison。
  2. 參考書籍
  3. ANTLR

基礎教學

  1. 撰寫 bas.y (yacc 檔) 和 bas.l (lex 檔)。
  2. yacc 編譯 bas.y 產生定義 token 的 y.tab.h 給 lex.yy.c include; 產生定義 parser 的 y.tab.c，yyparse 是 parser 的入口函式。
  3. lex 編譯 bas.l 產生定義 scanner 的 lex.yy.c，yylex 是 scanner 的入口函式。y.tab.c 的 yyparse 調用 yylex。
  4. cc (C 編譯器) 編譯 y.tab.c 和 lex.yy.c，得到自製編譯器 bas.exe。
  5. bas.exe 編譯 source，得到 compiled output。

BNF

Flex & Bison 應用

Flex

definitions
%%
rules
%%
user code
  • 常用選項
    • 16.3 Code-Level And API Options
      • %option bison-locations
        • 產生位置資訊供 bison 使用。此選項隱含 %option bison-bridge
      • %option bison-bridge
        • 產生適用於 bison 的接口。
      • %option reentrant
        • 產生可重入的 scanner。
      • %option nounistd
        • 避免引入非標準的 unistd 標頭檔。
      • %option noyywrap
      • %option nodefault
      • %option yylinenumber
      • %option case-insensitive
  • 小技巧
    • 10 Start Conditions
    • Lex 規則可以用 start condition 分組。start condition 可以是 inclusive 或是 exclusive。
      • 切換至 inclusive start condition 時，沒有隸屬任何 start condition 的規則也會被納入匹配。If the start condition is inclusive, then rules with no start conditions at all will also be active.
      • 切換至 exclusive start condition 時，只有隸屬該 exclusive start condition 會被納入匹配。If it is exclusive, then only rules qualified with the start condition will be active.
      • BEGIN(0) 或是 BEGIN(INITIAL) 都會切換回預設的 start condition (INITIAL)。
    • When should I use BEGIN to change start condition?
      %s example     ; example 是 inclusive start condition。
%%

; 當切換到 example start condition 時，foo 和 bar 都會被激活。   
<example>foo   do_something();
     
bar            something_else();
  • The quotation marks “ ” in flex
    • 雙引號用意在於告訴 lex 不用解釋其中內容。正則表達式所用的符號不起作用。
    • 如果要匹配雙引號，使用 \"。
    • 單引號不起作用，單純代表單引號本身。
    • Bison 用雙引號代表要匹配的字串，單引號代表要匹配的字元。

Bison

Bison 3.0 版之後有較大改變。注意手冊版本。

Each call to yylex() returns an integer value which represents a token type. This tells YACC what kind of token it has read. The token may optionally have a value, which should be placed in the variable yylval.

By default yylval is of type int, but you can override that from the YACC file by re#defining YYSTYPE.

  • token 有以下三種含義:
    • 回傳給 yacc 的 token type。
    • token 的原始字串，yytext。
    • 回傳給 yacc 的 token value，yylval。

使用 %union 讓 yylval 可以有多種型別。 

%union 
{
        int number;
        char *string;
}

%token <number> STATE
%token <number> NUMBER
%token <string> WORD

[0-9]+                  yylval.number=atoi(yytext); return NUMBER;
[a-z0-9]+               yylval.string=strdup(yytext);return WORD;

優先權與結合性

建立符號表

建立語法樹

Bison 中所寫的語法規則，有些僅是用來處理運算子優先順序，和程式無關。抽象語法樹即是將前述語法規則剔除。

  • 3 Using Bison

Mid-Rule Action

  • 3.4.8.1 Using Mid-Rule Actions
    • A mid-rule action may refer to the components preceding it using $n, but it may not refer to subsequent components because it is run before they are parsed.
      • mid-rule action 可以參照到前面 symbol 的值，但無法存取其後 symbol 的值。
    • The mid-rule action itself counts as one of the components of the rule. This makes a difference when there is another action later in the same rule (and usually there is another at the end): you have to count the actions along with the symbols when working out which number n to use in $n.
      • mid-rule action 本身也算成一個 symbol。
    • The mid-rule action can also have a semantic value. The action can set its value with an assignment to $$, and actions later in the rule can refer to the value using $n. Since there is no symbol to name the action, there is no way to declare a data type for the value in advance, so you must use the ‘$<…>n’ construct to specify a data type each time you refer to this value.
      • mid-rule action 本身可以有值。
    • There is no way to set the value of the entire rule with a mid-rule action, because assignments to $$ do not have that effect. The only way to set the value for the entire rule is with an ordinary action at the end of the rule.
      • mid-rule action 的值無法賦值給本身所屬的規則。

錯誤回報

If you invoke ‘%define parse.error verbose’ in the Bison declarations section (see The Bison Declarations Section), then Bison provides a more verbose and specific error message string instead of just plain "syntax error". However, that message sometimes contains incorrect information if LAC is not enabled (see LAC).

  • 8. Error Reporting and Recovery

記錄位置

  • lex 和 yacc 学习笔记5 （bison和flex 记录token的位置信息）
    • 要開啟 location 的支援，必須同時修改 flex 和 bison。
      • flex 添加 %option bison-locations (%option bison-bridge 可移除)。
      • flex 添加如下代碼:
        /* handle locations */
//static int yycloumn = 1; // yycloumn 自動產生
 
#define YY_USER_ACTION yylloc->first_line = yylloc->last_line = yylineno; \
    yylloc->first_column = yycloumn; yylloc->last_column = yycloumn+yyleng-1; \
    yycolumn += yyleng;
      • flex 在有處理 \n 的規則將 yycloumn 歸為 1。
      • bison 添加 %locations。函式 yyerror 第一個參數為 YYLTYPE*。
  • lex 把 ' ' 和 '\t' 都視做長度為一，所以針對 '\t' 計算位置會有問題。

上下文相關語法

錯誤回復

  • 3.7.6 Freeing Discarded Symbols
    • 進行錯誤回復的過程中，yacc 可能會丟棄已處理的 symbol。此時需要將被丟棄的 symbol 使用的內存釋放掉。

衝突處理

根本原因: 當 Bison 試圖 reduce 時，有其它 shift 或是 reduce 的可能，即為 shift/reduce 或是 reduce/reduce conflict。以下圖來看，"." 出現在規則結尾處時，代表有 reduce 發生。此時，如果有其它 "." 出現，代表衝突發生。 

State 14 conflicts: 1 shift/reduce

   ...
   
State 14

   12 input_state_path: T_INPUT_STATE_NO_PATH . T_DIVIDE identifier
   13                 | T_INPUT_STATE_NO_PATH .

    T_DIVIDE  shift, and go to state 19

    T_DIVIDE  [reduce using rule 13 (input_state_path)]
    $default  reduce using rule 13 (input_state_path)
  • . 代表目前正讀入 T_INPUT_STATE_NO_PATH，規則 12 和規則 13 同時處於此狀態 (State 14)。
  • 如果下一個 token 是 T_DIVIDE，Bison 可以選擇使用規則 12，shift T_DIVIDE，轉換到狀態 19。
  • 如果下一個 token 是 T_DIVIDE，Bison 可以選擇使用規則 13，reduce。
  • 對於 shift/reduce conflict，Bison 預設選擇 shift。因此沒有被用到的規則 13，以中括號表示。
  • shift/reduce conflict
    • Bison 預設選擇 shift
    • 解決方法:
      • 從 *.output 檔找到有 shift/reduce conflict 的狀態。
      • 辨識出 reduce rule。
      • 辨識出與之相衝突的 shift rule。"reduce using" 語句前面有 reduce 預期的下一個 token，看哪一條 shift 預期的下一個 token 和它相同。
      • 辨識出 reduce rule 會 reduce 到的狀態。
      • 推導出導致 shift/reduce conflict 的字串。
  • reduce/reduce conflict
    • Bison 預設選擇第一條規則 reduce
  • 容易發生衝突的情況 (基本上都是因為 recursive 性質所引起):
    • expression grammers: 同一條規則，但此規則屬於 recursive rule，因此衝突有機會發生在同一條規則上。
    • if/then/else: 具有相同 LHS 的規則。
    • nest lists of items
$ grep "State 14" -n Syntax_InputState.output
$ sed -n '211,222p' Syntax_InputState.output > Syntax_InputState.output.new

GLR 剖析器

  • Bison 是 LALR(1)，1 代表 lookahead 的 token 個數為 1。如果文法需要 2 個 lookahead，考慮改用 GLR。

對於原本文法存在的 shift/reduce 或是 reduce/reduce conflict，GLR parser 於衝突處分成多個 parser 同時並行處理。注意! GLR parser 處理時間隨 conflict 個數增加。 

%glr-parser
%expect 2
%expect-rr

Additional syntax error message on GLR parser when syntax is ambiguous

  • 使用 %dprec 解決 reduce/reduce conflict
  • 使用 %merge

Q & A

處理 INCLUDE

YY_BUFFER_STATE 是 lex 對特定輸入流所產生的句柄。其中包含輸入流的緩衝區，和其它相關變數。 

#define YY_STRUCT_YY_BUFFER_STATE
struct yy_buffer_state
    {
    FILE *yy_input_file;
 
    char *yy_ch_buf;        /* input buffer */
    char *yy_buf_pos;       /* current position in input buffer */
 
    /* Size of input buffer in bytes, not including room for EOB
     * characters.
     */
    yy_size_t yy_buf_size;
 
    ...
}
  • Chapter 2: Using Flex
    • Start States and Nested Input Files
  • Chapter 5: A Reference for Flex Specifications
    • Input Management
  • Lex 的輸入流可以是:
  • YYINPUT 將輸入流填充到緩衝區，使用者可以自行替換 YYINPUT，添加自己所需的功能。
yy_switch_to_buffer (yy_scan_buffer (char *base, yy_size_t size) );
  • 第零階段。處理巨集定義和調用、條件編譯。

Lex & Yacc Internal

Flex

token 由兩部分組成: token 和 token value。

  • Lex
    • yytext: token
    • yylval: token value，傳給 yacc
    • yylex: lexer
      %{
// declaration and option setting
#include <stdio.h>
#include <y.tab.h>    // yacc 根據 *.y 產生的 *.h，定義 token (number)
%}

%%
// pattern and action
REGEXP1     ACTION

REGEXP2     {ACTIONS}

%%
// helper function
  • Yacc
    • YYSTYPE 定義 yylval 的型別，這裡用改用 union
    • 用 $- 取得第幾號 yylval
    • yyparse: parser
      %{
// include C header files
%}

// 定義 token。parser 據此判斷該符號是 token。
// 其餘非 token 的符號必須出現在 rule 左邊至少一次。

%%

// rule (grammer)

// EXPS     ($$)
// EXP      ($1)
// FACTORS  ($2)
// TOKEN    ($3)
EXPS: /* empty, match the beginning of the input */
  | EXP FACTORS TOKEN
    {
        ACTIONS
    }
; /* end of rule */    
%%
// helper function
  • lex 可以設定多種 start condition。不同 start condition 會採用不同的 rule。使用 BEGIN 切換 start condition。
%x SN_CONDITION_MACRO_DEFINITION    SN_CONDITION_MACRO_CALL  SN_CONDITION_MACRO_CALL_DELIM
%x SN_CONDITION_MACRO_EXPANSION     SN_CONDITION_MACRO_DECL  SN_CONDITION_INCLUDE
%x SN_CONDITION_FALSE
%x SN_CONDITION_COPY                SN_CONDITION_MESSAGE
%x SN_NO_BOUNDARY_TWO_STRING        SN_NO_BOUNDARY_ONE_STRING
%x SN_COMMENT_CONDITION             SN_COMMENT_CONDITION2
%x SN_NO_BOUNDARY_THREE_TOKEN
  • yyscan_t 是可重入 (reentrant) 的 Lex 之狀態。
// 透過 yyscan_t 傳遞 scanner 狀態
//  struct yyguts_t * yyg = (struct yyguts_t*)yyscanner;
typedef void* yyscan_t;
 
/* For convenience, these vars (plus the bison vars far below)
   are macros in the reentrant scanner. */
#define yyin yyg->yyin_r
#define yyout yyg->yyout_r
#define yyextra yyg->yyextra_r
#define yyleng yyg->yyleng_r
#define yytext yyg->yytext_r
#define yylineno (YY_CURRENT_BUFFER_LVALUE->yy_bs_lineno)
#define yycolumn (YY_CURRENT_BUFFER_LVALUE->yy_bs_column)
#define yy_flex_debug yyg->yy_flex_debug_r
 
/* Holds the entire state of the reentrant scanner. */
struct yyguts_t
    {
    /* User-defined. Not touched by flex. */
    YY_EXTRA_TYPE yyextra_r;
 
    /* The rest are the same as the globals declared in the non-reentrant scanner. */
    FILE *yyin_r, *yyout_r;
    size_t yy_buffer_stack_top; /**< index of top of stack. */
    size_t yy_buffer_stack_max; /**< capacity of stack. */
    YY_BUFFER_STATE * yy_buffer_stack; /**< Stack as an array. */
    char yy_hold_char;
    int yy_n_chars;
    int yyleng_r;
    char *yy_c_buf_p;
    int yy_init;
    int yy_start;
    int yy_did_buffer_switch_on_eof;
    int yy_start_stack_ptr;
    int yy_start_stack_depth;
    int *yy_start_stack;
    yy_state_type yy_last_accepting_state;
    char* yy_last_accepting_cpos;
 
    int yylineno_r;
    int yy_flex_debug_r;
 
    char *yytext_r;
    int yy_more_flag;
    int yy_more_len;
 
    YYSTYPE * yylval_r;
 
    }; /* end struct yyguts_t */

Bison

系列文章

網路教程

進階議題

  • GLR parser
  • Push and Pull parser
    • 以 parser 為主，調用 scanner 的模式，稱之為 pull parser，意味著將 token pull 進 parser。
    • 以 scanner 為主，將 token 餵給 scanner 的模式，稱之為 push parser，意味著將 token push 進 parser。

斷行問題

編碼問題

語法剖析術語

外部連結

登录