原作：2019～2021年

此次共享，騰訊內(nèi)網(wǎng) / 外網(wǎng)同步發(fā)布。

內(nèi)部代碼地址：https://git.code.oa.com/fatboyli/QBDF

外部代碼地址：GitHub - ventureli/QBDF

兩年前的一個(gè)混淆包（無源碼）：GitHub - ventureli/VLOCInterpreter

作者：騰訊fatboyli（李文強(qiáng)）

說到這個(gè)章節(jié)，我特別的煩躁，主要還有兩個(gè)原因，1.涉及的理論有點(diǎn)多。2.其實(shí)我也沒完全搞明白，反正就是從實(shí)用性出發(fā)，最后也寫出來了，所以這章節(jié)我可能會(huì)有些概念闡釋的不是很清楚，甚至是錯(cuò)誤的，但是最重要的我會(huì)很明白的說明QBDF是怎么完成的。

BNF：巴科斯范式（BNF是Backus-Naur form首字母的縮寫）

一種形式化的語法表示方法，用來描述語法的一種形式體系，是一種典型的元語言。又稱巴科斯-諾爾形式(Backus-Naur form)。它不僅能嚴(yán)格地表示語法規(guī)則，而且所描述的語法是與上下文無關(guān)的。它具有語法簡單，表示明確，便于語法分析和編譯的特點(diǎn)。它以遞歸方式描述語言中的各種成分的。

在雙引號中的字"word"代表著這些字符本身。而double_quote用來代表雙引號；

在雙引號外的字（有可能有下劃線）代表著語法部分；

尖括號<>內(nèi)包含的為必選項(xiàng)；方括號[]內(nèi)包含的為可選項(xiàng)；

大括號{}內(nèi)包含的為可重復(fù)0至無數(shù)次的項(xiàng)；

圓括號()內(nèi)包含的所有項(xiàng)為一組，用來控制表達(dá)式的優(yōu)先級；

豎線|表示在其左右兩邊任選一項(xiàng)，相當(dāng)于"OR"的意思；::=是“被定義為”的意思；

...表示術(shù)語符號；

斜體字:參數(shù)，在其它地方有解釋；

舉個(gè)例子：比如一個(gè)簡單得數(shù)字的表達(dá)方式：

數(shù)字> ::= 0x<十六進(jìn)制數(shù)字串> | 0<八進(jìn)制數(shù)字串> | <十進(jìn)制數(shù)字串>?

　　<十六進(jìn)制數(shù)字串> ::= <十六進(jìn)制數(shù)字> | <十六進(jìn)制數(shù)字串><十六進(jìn)制數(shù)字>?

　　<八進(jìn)制數(shù)字串> ::= <八進(jìn)制數(shù)字> | <八進(jìn)制數(shù)字串><八進(jìn)制數(shù)字>?

　　<十進(jìn)制數(shù)字串> ::= <十進(jìn)制數(shù)字> | <十進(jìn)制數(shù)字串><十進(jìn)制數(shù)字>?

　　<十六進(jìn)制數(shù)字> ::= <十進(jìn)制數(shù)字> | A | B | C | D | E | F?

　　<十進(jìn)制數(shù)字> ::= <八進(jìn)制數(shù)字> | 8 | 9?

　　<八進(jìn)制數(shù)字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7?

通過以上的描述其實(shí)我們能很清楚的理解一個(gè)數(shù)字是怎么構(gòu)成的。

語法解析是一個(gè)聽起來不是很復(fù)雜但是一旦開始寫程序就無從下手的功能。如果沒有完成的理論結(jié)構(gòu)去支持，我們就只能用IF-ELSE 這種去處理，最后發(fā)現(xiàn)怎么寫都不對，總有例外的情況，無論往探測多少個(gè)單詞都沒辦法解決語法遞歸的問題。（我一開始就是這么弄的）只能回過頭來先搞定BNF，然后按照他的指導(dǎo)，寫起代碼來就非常簡單了。

說起這個(gè)比較慚愧，我不會(huì)寫B(tài)NF，在做QBDF的過程中，雖然重新研究了下編譯原理，但是也沒把握重新搞定整個(gè)BNF的編寫，所以只能從已有的開源的BNF表達(dá)式中改寫。主要有一下兩個(gè)考慮。

1）我們需要一個(gè)簡化了的OC語法集合，比如NotNull，enum這種第一版本完全可以拋棄掉，因?yàn)檫@些語法結(jié)構(gòu)并不影響能力的無限性，只是在書寫OC代碼的時(shí)候減少便捷性。這個(gè)是完全可以接受的。畢竟這是一個(gè)內(nèi)部人用的框架。

2）OC語法來源與C，表達(dá)式的文法完全可以采用C的。

3）OC的特有的語法屬性非常的明顯（比如@interface 開頭，‘-（’ ，'[標(biāo)示符' 開頭等）而且他們存在的地方都是最高的運(yùn)算符優(yōu)先級，可以完全當(dāng)作原子操作。

所以我當(dāng)時(shí)采用C89的BNF，然后進(jìn)行了小改動(dòng)使其支持QBDF的OC語法。由于年代久遠(yuǎn)我也也不是特別的確認(rèn)這是C89的。但是我從網(wǎng)上搜索后，發(fā)現(xiàn)這個(gè)確實(shí)可以用。

translation_unit : external_decl

| translation_unit external_decl

;

external_decl? ? ? ? : function_definition

| decl

;

function_definition? ? : decl_specs declarator decl_list compound_stat

|? ? ? ? declarator decl_list compound_stat

| decl_specs declarator? ? ? ? compound_stat

|? ? ? ? declarator? ? compound_stat

;

decl? ? ? ? ? ? : decl_specs init_declarator_list ';'

| decl_specs? ? ? ? ? ? ';'

;

decl_list? ? ? ? : decl

| decl_list decl

;

decl_specs? ? ? ? : storage_class_spec decl_specs

| storage_class_spec

| type_spec decl_specs

| type_spec

| type_qualifier decl_specs

| type_qualifier

;

storage_class_spec? ? : 'auto' | 'register' | 'static' | 'extern' | 'typedef'

;

type_spec? ? ? ? : 'void' | 'char' | 'short' | 'int' | 'long' | 'float'

| 'double' | 'signed' | 'unsigned'

| struct_or_union_spec

| enum_spec

| typedef_name

;

type_qualifier? ? ? ? : 'const' | 'volatile'

;

struct_or_union_spec? ? : struct_or_union id '{' struct_decl_list '}'

| struct_or_union? ? '{' struct_decl_list '}'

| struct_or_union id

;

struct_or_union? ? ? ? : 'struct' | 'union'

;

struct_decl_list? ? : struct_decl

| struct_decl_list struct_decl

;

init_declarator_list? ? : init_declarator

| init_declarator_list ',' init_declarator

;

init_declarator? ? ? ? : declarator

| declarator '=' initializer

;

struct_decl? ? ? ? : spec_qualifier_list struct_declarator_list ';'

;

spec_qualifier_list? ? : type_spec spec_qualifier_list

| type_spec

| type_qualifier spec_qualifier_list

| type_qualifier

;

struct_declarator_list? ? : struct_declarator

| struct_declarator_list ',' struct_declarator

;

struct_declarator? ? : declarator

| declarator ':' const_exp

|? ? ? ? ':' const_exp

;

enum_spec? ? ? ? : 'enum' id '{' enumerator_list '}'

| 'enum'? ? '{' enumerator_list '}'

| 'enum' id

;

enumerator_list? ? ? ? : enumerator

| enumerator_list ',' enumerator

;

enumerator? ? ? ? : id

| id '=' const_exp

;

declarator? ? ? ? : pointer direct_declarator

|? ? direct_declarator

;

direct_declarator? ? : id

| '(' declarator ')'

| direct_declarator '[' const_exp ']'

| direct_declarator '['? ? ? ? ']'

| direct_declarator '(' param_type_list ')'

| direct_declarator '(' id_list ')'

| direct_declarator '('? ? ? ? ')'

;

pointer? ? ? ? ? ? : '*' type_qualifier_list

| '*'

| '*' type_qualifier_list pointer

| '*'? ? ? ? ? ? pointer

;

type_qualifier_list? ? : type_qualifier

| type_qualifier_list type_qualifier

;

param_type_list? ? ? ? : param_list

| param_list ',' '...'

;

param_list? ? ? ? : param_decl

| param_list ',' param_decl

;

param_decl? ? ? ? : decl_specs declarator

| decl_specs abstract_declarator

| decl_specs

;

id_list? ? ? ? ? ? : id

| id_list ',' id

;

initializer? ? ? ? : assignment_exp

| '{' initializer_list '}'

| '{' initializer_list ',' '}'

;

initializer_list? ? : initializer

| initializer_list ',' initializer

;

type_name? ? ? ? : spec_qualifier_list abstract_declarator

| spec_qualifier_list

;

abstract_declarator? ? : pointer

| pointer direct_abstract_declarator

|? ? direct_abstract_declarator

;

direct_abstract_declarator: '(' abstract_declarator ')'

| direct_abstract_declarator '[' const_exp ']'

|? ? ? ? ? ? ? ? '[' const_exp ']'

| direct_abstract_declarator '['? ? ']'

|? ? ? ? ? ? ? ? '['? ? ']'

| direct_abstract_declarator '(' param_type_list ')'

|? ? ? ? ? ? ? ? '(' param_type_list ')'

| direct_abstract_declarator '('? ? ? ? ')'

|? ? ? ? ? ? ? ? '('? ? ? ? ')'

;

typedef_name? ? ? ? : id

;

stat? ? ? ? ? ? : labeled_stat

| exp_stat

| compound_stat

| selection_stat

| iteration_stat

| jump_stat

;

labeled_stat? ? ? ? : id ':' stat

| 'case' const_exp ':' stat

| 'default' ':' stat

;

exp_stat? ? ? ? : exp ';'

|? ? ';'

;

compound_stat? ? ? ? : '{' decl_list stat_list '}'

| '{'? ? ? ? stat_list '}'

| '{' decl_list? ? ? ? '}'

| '{'? ? ? ? ? ? '}'

;

stat_list? ? ? ? : stat

| stat_list stat

;

selection_stat? ? ? ? : 'if' '(' exp ')' stat

| 'if' '(' exp ')' stat 'else' stat

| 'switch' '(' exp ')' stat

;

iteration_stat? ? ? ? : 'while' '(' exp ')' stat

| 'do' stat 'while' '(' exp ')' ';'

| 'for' '(' exp ';' exp ';' exp ')' stat

| 'for' '(' exp ';' exp ';'? ? ')' stat

| 'for' '(' exp ';'? ? ';' exp ')' stat

| 'for' '(' exp ';'? ? ';'? ? ')' stat

| 'for' '('? ? ';' exp ';' exp ')' stat

| 'for' '('? ? ';' exp ';'? ? ')' stat

| 'for' '('? ? ';'? ? ';' exp ')' stat

| 'for' '('? ? ';'? ? ';'? ? ')' stat

;

jump_stat? ? ? ? : 'goto' id ';'

| 'continue' ';'

| 'break' ';'

| 'return' exp ';'

| 'return'? ? ';'

;

exp? ? ? ? ? ? : assignment_exp

| exp ',' assignment_exp

;

assignment_exp? ? ? ? : conditional_exp

| unary_exp assignment_operator assignment_exp

;

assignment_operator? ? : '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<='

| '>>=' | '&=' | '^=' | '|='

;

conditional_exp? ? ? ? : logical_or_exp

| logical_or_exp '?' exp ':' conditional_exp

;

const_exp? ? ? ? : conditional_exp

;

logical_or_exp? ? ? ? : logical_and_exp

| logical_or_exp '||' logical_and_exp

;

logical_and_exp? ? ? ? : inclusive_or_exp

| logical_and_exp '&&' inclusive_or_exp

;

inclusive_or_exp? ? : exclusive_or_exp

| inclusive_or_exp '|' exclusive_or_exp

;

exclusive_or_exp? ? : and_exp

| exclusive_or_exp '^' and_exp

;

and_exp? ? ? ? ? ? : equality_exp

| and_exp '&' equality_exp

;

equality_exp? ? ? ? : relational_exp

| equality_exp '==' relational_exp

| equality_exp '!=' relational_exp

;

relational_exp? ? ? ? : shift_expression

| relational_exp '<' shift_expression

| relational_exp '>' shift_expression

| relational_exp '<=' shift_expression

| relational_exp '>=' shift_expression

;

shift_expression? ? : additive_exp

| shift_expression '<<' additive_exp

| shift_expression '>>' additive_exp

;

additive_exp? ? ? ? : mult_exp

| additive_exp '+' mult_exp

| additive_exp '-' mult_exp

;

mult_exp? ? ? ? : cast_exp

| mult_exp '*' cast_exp

| mult_exp '/' cast_exp

| mult_exp '%' cast_exp

;

cast_exp? ? ? ? : unary_exp

| '(' type_name ')' cast_exp

;

unary_exp? ? ? ? : postfix_exp

| '++' unary_exp

| '--' unary_exp

| unary_operator cast_exp

| 'sizeof' unary_exp

| 'sizeof' '(' type_name ')'

;

unary_operator? ? ? ? : '&' | '*' | '+' | '-' | '~' | '!'

;

postfix_exp? ? ? ? : primary_exp

| postfix_exp '[' exp ']'

| postfix_exp '(' argument_exp_list ')'

| postfix_exp '('? ? ? ? ? ? ')'

| postfix_exp '.' id

| postfix_exp '->' id

| postfix_exp '++'

| postfix_exp '--'

;

primary_exp? ? ? ? : id

| const

| string

| '(' exp ')'

;

argument_exp_list? ? : assignment_exp

| argument_exp_list ',' assignment_exp

;

const? ? ? ? ? ? : int_const

| char_const

| float_const

| enumeration_const

;

然后對這個(gè)進(jìn)行小幅度更改即可。比如針對 后綴表達(dá)式，我們做了更改如下：

/*

?postfix-expression:

(identifier | constant | string | "(" expression ")" | [identify OCArglist]

?"[" expression "]"? ? ? ? ? ? |

?"(" assignment-expression% ")" |

?"." identifier? ? ? ? ? ? ? ? |

?"->" identifier? ? ? ? ? ? ? ? |

?"++"? ? ? ? ? ? ? ? ? ? ? ? ? |

?"--"

?"^(assignment-expression){}"? | block 作為一個(gè)獨(dú)立的結(jié)構(gòu)不單獨(dú)解析了，代碼放在外面

?)*

?OCArglist:

? ? identify | (_QBDF_EXP_Postfix:expression)*

??*/

這樣就完全把? "[[UIView alloc] initWithFrame:xxxx]"? 給包括進(jìn)去了。所以整體改動(dòng)非常小。這里有同學(xué)可能要問了，那些“類定義”，“protocol 定義”，“類實(shí)現(xiàn)”這些代碼不是C里的BNF啊，要怎么處理呢？

這個(gè)回答其實(shí)很簡單，這就是我學(xué)了個(gè)這個(gè)半吊子編譯原理的菜鳥的折中方法（這個(gè)項(xiàng)目我當(dāng)初只寫了不到兩個(gè)半月，這里確實(shí)沒設(shè)計(jì)好。）我在第一個(gè)BNF表達(dá)式里，就是translation_unit 這個(gè)定義對應(yīng)的遞歸子程序?qū)崿F(xiàn)里就處理掉了。怎么處理的呢？大家還記得在上一章節(jié)我在做詞法分析的時(shí)候 把“@interface”這種字符串給組成一個(gè)特殊的單詞。那么只要由個(gè)數(shù)單詞開頭的token，肯定要進(jìn)入到不同的分支里了。代碼如下。其實(shí)就是

語法解析入口程序

好了這一章節(jié)就到此結(jié)束了，我深知這一章節(jié)我講的很不好，大家興趣還是去看看“編譯原理”的課件，我看的是哈工大版本的，就能明白了。我也不是很懂那么復(fù)雜的理論（鞠躬）！

?

總結(jié)

以上是生活随笔為你收集整理的QQ浏览器HD iOS 动态化/热修复方案QBDF解释器-从C89简化的BNF范式（4）【简书被冻结-搬运】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。