說到ParserGenerator不得不提的是BNF,應此QParserGenerator也有它自己的BNF,這時有人會問BNF究竟是什么呢?簡單的說BNF就是用來描述一種語法的東西,比如在Basic中If后面跟表達式然后是Then中間是語句塊末尾必須要有End If等等的一系列描述,更專業的解釋我們可以看一下維基百科上的解釋。
好了,說完了BNF那讓我們來看一下QParserGenerator的BNF到底是長啥樣的
%token "%" "token" "start" "|" "-" ">" ";" "[" "]";
%start start;
strings -> strings "{String}"
| "{String}"
;
vs -> vs "{Letter}"
| vs "{String}"
| "{Letter}"
| "{String}"
;
option -> "[" vs "]"
;
oneProductionRight -> oneProductionRight option
| oneProductionRight vs
| option
| vs
;
someProductionRight -> someProductionRight "|" oneProductionRight
| oneProductionRight
;
token -> "%" "token" strings ";"
;
someTokens -> someTokens token
| token
;
production -> "{Letter}" "-" ">" someProductionRight ";"
;
someProductions -> someProductions production
| production
;
start -> someTokens "%" "start" "{Letter}" ";" someProductions
| "%" "start" "{Letter}" ";" someProductions
;
也許有人會問,不對啊根據維基百科上的說明BNF不應該是長這樣的,其實QParserGenerator是一個BNF的生成器,它可以將輸入的BNF通過一系列的運算最后生成LALR(1)分析表,為了BNF文件的美觀和方便處理我特地把他設計成了這個樣子的而已,好了下面我們就以這個BNF文件來說明應該如何來書寫BNF文件。%start start;
strings -> strings "{String}"
| "{String}"
;
vs -> vs "{Letter}"
| vs "{String}"
| "{Letter}"
| "{String}"
;
option -> "[" vs "]"
;
oneProductionRight -> oneProductionRight option
| oneProductionRight vs
| option
| vs
;
someProductionRight -> someProductionRight "|" oneProductionRight
| oneProductionRight
;
token -> "%" "token" strings ";"
;
someTokens -> someTokens token
| token
;
production -> "{Letter}" "-" ">" someProductionRight ";"
;
someProductions -> someProductions production
| production
;
start -> someTokens "%" "start" "{Letter}" ";" someProductions
| "%" "start" "{Letter}" ";" someProductions
;
首先可以看到最頂上有一些以%token開頭的字符串(在C語言中我們將用雙引號括起來的字符序列稱為字符串)以及最后的一個分號,其實這里的這些字符串正是BNF中說說的終結符,所以我們規定,所有其他沒用%token聲明的符號都是非終結符。終結符是用來做移進操作的,在某種特定的語言中他表現為一個token,而非終結符可以理解為一個代詞,通常一個非終結符都可以展開為一條或多條規則(產生式)。至于說為什么每條內容后面都會有分號呢,只是為了處理上的方便(消除語法上的沖突?)。
好了,我們把終結符和非終結符這兩個專業術語給解釋完了,接下來可以看到的是一個以%start開頭后跟一個非終結符的語句,他表明了所有規則(產生式)是從哪里開始的(有始無終的節奏-_-||杯具啊)。
最后就是我們的重頭了,多空一行也不為過吧。這里有一大堆的產生式,那我們如何來閱讀他呢,其實上面已經介紹了有個表明了所有規則開頭的非終結符,好那讓我們來找一下他所對應的產生式在哪里
start -> someTokens "%" "start" "{Letter}" ";" someProductions
| "%" "start" "{Letter}" ";" someProductions
;
可以看到所有的規則可分為左半部分和右半部分,左邊總是一個非終結符來說明他應該被哪一些規則來替代,而右邊則是這些規則的具體內容包含了一些終結符和非終結符序列,中間則用一個箭頭符號來分割。在所有的規則中非終結符都是不帶引號的,而終結符都是用引號將其括起來的,在終結符中有一些內置的變量來表達一些特定的表達式,這個會在下文中做出說明。當然對于同一個終結符來說我們可以用任意多個規則來說明他,他們都是或的關系,由于BNF中不可能存在且的關系,應此我們并不需要考慮他。| "%" "start" "{Letter}" ";" someProductions
;
下面讓我們來看一下預定義的終結符有哪些,從Parser.cpp的代碼中可知預定義的終結符有"{String}"、"{Digit}"、"{Real}"、"{Letter}"。
"{String}":表示正則表達式\"[^\"]*\"
"{Digit}":表示正則表達式[0-9]+
"{Real}":表示正則表達式[0-9]*.[0-9]+
"{Letter}":表示正則表達式((_[0-9]+)|([_a-zA-Z]+))[_0-9a-zA-Z]*
從這些正則表達式中可見"{String}"表示一個帶雙引號的字符串,"{Digit}"則表示一個數字,"{Real}"則表示一個浮點數,"{Letter}"則表示一個不帶雙引號的字符串。當然這些正則表達式寫的并不完備,比如"{String}"中沒有支持轉義等等。
然后讓我們來看一下每條規則支持哪些語法,首先從下面幾條文法中可知,可用方括號將一些可選項括起來。
1 vs -> vs "{Letter}"
2 | vs "{String}"
3 | "{Letter}"
4 | "{String}"
5 ;
6
7 option -> "[" vs "]"
8 ;
2 | vs "{String}"
3 | "{Letter}"
4 | "{String}"
5 ;
6
7 option -> "[" vs "]"
8 ;
而對于一個規則來說他可以用若干條產生式來說明他,其中每條產生式之間是或的關系。
1 oneProductionRight -> oneProductionRight option
2 | oneProductionRight vs
3 | option
4 | vs
5 ;
6
7 someProductionRight -> someProductionRight "|" oneProductionRight
8 | oneProductionRight
9 ;
2 | oneProductionRight vs
3 | option
4 | vs
5 ;
6
7 someProductionRight -> someProductionRight "|" oneProductionRight
8 | oneProductionRight
9 ;
其他一些規則則說明了一些上文提到的規則,比如開頭是一些token的定義等。終于把QParserGenerator的文法文件的結構給介紹完了,在接下來的一篇文章中我們將介紹如何用QParserGenerator來生成一個帶括號優先級的四則混合運算計算器,其文法可見Calculator.txt,QLanguage整個項目的代碼可見https://github.com/lwch/QLanguage/。