前言

前言:詞法分析和語(yǔ)法分析部分的設(shè)計(jì),和在實(shí)際編程過(guò)程中,編譯期的語(yǔ)法檢查和相關(guān)的錯(cuò)誤提示是息息相關(guān)的
此篇可以看做是《自制編譯器》的讀書(shū)筆記,內(nèi)部一些舉例,例如stmts是在Cb語(yǔ)言?xún)?nèi)的描述,在C或者OC的編譯器中名字未必一致,但是功能是相通的.

詞法分析

基于EBNF的語(yǔ)法描述

以下這些是比較簡(jiǎn)單的邏輯概念,很容易理解

種類(lèi)	舉例
終端符	<IDENTIFIER> 或 ","
非終端符	name()
連接	<UNSIGNED><LONG>
重復(fù) 0 次或多次	(","expr())*
重復(fù) 1 次或多次	(stmt())+
選擇	<CHAR> \| <SHORT> \| <INT> \| <LONG>
可以省略	[<ELSE> stmt()]

語(yǔ)法的二義性和token的超前掃描

空懸else

舉個(gè)例子,如果規(guī)則設(shè)計(jì)為"if" "(" expr() ")" stmt() ["else" stmt()]
以下兩種寫(xiě)法都符合以上規(guī)則:

寫(xiě)法1
if (cond1) {
      if (cond2) {
          f();
      } else {
          g();
} }

寫(xiě)法2
if (cond1) {
      if (cond2) {
        f();
       }
} else {
  g();
 }

對(duì)應(yīng)兩種解釋的語(yǔ)法樹(shù)

if 語(yǔ)句的規(guī)則存在二義性的問(wèn)題是比較有名的，俗稱(chēng)空懸 else(dangling else).

選擇沖突

type(): {} {
      <SIGNED> <CHAR>
    | <SIGNED> <SHORT>
    | <SIGNED> <INT>
    | <SIGNED> <LONG>
......

事實(shí)上, 在遇到用“|”分隔的選項(xiàng)時(shí)，在僅讀取了 1 個(gè) token 的時(shí)刻就會(huì)對(duì)選項(xiàng)進(jìn) 行判斷，確切的動(dòng)作如下所示。

讀取1個(gè)token
按照書(shū)寫(xiě)順序依次查找由上述 token 開(kāi)頭的選項(xiàng)
找到的話(huà)就選用該選項(xiàng)

也就是說(shuō),根據(jù)上述規(guī)則, 在讀取了 <SIGNED> token 時(shí)就已經(jīng)選擇了 <SIGNED> <CHAR>,因此即便寫(xiě)了選項(xiàng) 2 和選項(xiàng) 3，也是完全沒(méi)有意義的。這個(gè)問(wèn)題稱(chēng)選擇沖突(choice conflict)

token的超前掃描

之前提到了在遇到選項(xiàng)時(shí)僅根據(jù)讀取的 1 個(gè) token 來(lái)判斷選擇哪個(gè)選項(xiàng).事實(shí)上這只是因?yàn)閮H根據(jù)讀取的 1 個(gè) token 進(jìn)行判斷.只要明確指定,可以在讀取更多的 token 后再?zèng)Q定選擇哪個(gè)選項(xiàng)。這個(gè)功能就稱(chēng)為 token 的超前掃描 (lookahead)

剛才列舉的語(yǔ)法規(guī)則也能夠用 token 的超前掃描進(jìn)行分析

type(): {}
{
  LOOKAHEAD(2) <SIGNED> <CHAR>
| LOOKAHEAD(2) <SIGNED> <SHORT>
| LOOKAHEAD(2) <SIGNED> <INT>
| <SIGNED> <LONG>
以下省略

添加的 LOOKAHEAD(2) 是關(guān)鍵.LOOKAHEAD(2) 表示的意思為“讀取 2 個(gè) token 后,如果讀取的 token 和該選項(xiàng)相符合,則選擇該選項(xiàng)”
也就是說(shuō),讀取 2 個(gè) token,如果它們是 <SIGNED> 和 <CHAR> 的話(huà)，就選用選項(xiàng) 1.同樣,第 2 個(gè)選項(xiàng)的意思是讀取 2 個(gè) token,如果它們是 <SIGNED> 和 <SHORT> 的話(huà),就選用選項(xiàng) 2
需要超前掃描的 token 個(gè)數(shù)(上述例子中為 2)是通過(guò)“共通部分的 token 數(shù) +1”這樣的算式計(jì)算得到的

可以省略的規(guī)則和沖突

除“選擇”以外，選擇沖突在“可以省略”或“重復(fù) 0 次或多次”中也可能發(fā)生。
可以省略的規(guī)則中，會(huì)發(fā)生“是省略還是不省略”的沖突，而非“選擇選項(xiàng) 1 還是選項(xiàng) 2”的沖突。之前提到的空懸 else 就是一個(gè)具體的例子

空懸 else 最直觀的判斷方法是“else 屬于最內(nèi)側(cè)的 if”,因此試著使用 LOOKAHEAD 來(lái)進(jìn) 行判斷.首先,未使用 LOOKAHEAD 進(jìn)行判斷的規(guī)則描述如下所示

if_stmt(): {}
  {
      <IF> "(" expr() ")" stmt() [<ELSE> stmt()]
  }

使用LOOKAHEAD來(lái)避免沖突發(fā)生的規(guī)則如下

if_stmt(): {}
  {
      <IF> "(" expr() ")" stmt() [LOOKAEHAD(1) <ELSE> stmt()]
  }

如你所見(jiàn),判斷方法本身非常簡(jiǎn)單.通過(guò)添加 LOOKAHEAD(1),就可以指定“讀取 1 個(gè) token后,如果該token符合規(guī)則(即如果是<ELSE>)則不省略<ELSE> stmt()”.這樣就能明確 else 始終屬于最內(nèi)側(cè)的 if 語(yǔ)句，空懸 else 的問(wèn)題就可以解決了

重復(fù)和沖突

重復(fù)的情況下會(huì)發(fā)生“是作為重復(fù)的一部分讀入還是跳出重復(fù)”這樣的選擇沖突。來(lái)看一個(gè)具體的例子，如下所示為 C? 中表示函數(shù)形參的聲明規(guī)則。

  param_decls(): {}
  {
      type() ("," type())* ["," "..."]
  }

這個(gè)規(guī)則中，表示可變長(zhǎng)參數(shù)的"," "..."不會(huì)被解析
因?yàn)楦鶕?jù)上述規(guī)則，在讀取 type() 后又讀到 "," 時(shí)，本來(lái)可能是 "," type() 也可能是 "..." 的,但默認(rèn)向前只讀取 1 個(gè) token,因此在讀到 "," 時(shí)就必須判斷是繼續(xù) 重復(fù)還是跳出重復(fù)。并且恰巧","和("," type())的開(kāi)頭一致，所以會(huì)一直判斷為重復(fù) ("," type())*，而規(guī)則 "," "..." 則完全不會(huì)被用到。實(shí)際上如果程序中出現(xiàn) ","
"..."，會(huì)因?yàn)椴环弦?guī)則"," type()而判定為語(yǔ)法錯(cuò)誤。要解決上述問(wèn)題，可以如下添加 LOOKAHEAD。

  param_decls(): {}
  {
      type() (LOOKAHEAD(2) "," type())* ["," "..."]
  }

這樣在每次判斷該重復(fù)時(shí)就會(huì)在讀取 2 個(gè) token 后再判斷是否繼續(xù)重復(fù)，因此在輸入了"," "..."后就會(huì)因?yàn)闄z測(cè)到和"," type()不匹配而跳出("," type())*的重復(fù)

更靈活的超前掃描

關(guān)于 token 的超前掃描,還有更為靈活的方法。之前提到的 LOOKAHEAD 可以指定“恰好讀取了幾個(gè) token”，除此之外還可以指定“讀取符合這個(gè)規(guī)則的所有 token”
舉例

definition(): {}
  {
storage() type() <IDENTIFIER> ";"
| storage() type() <IDENTIFIER> arg_decls() block() 以下省略

除了提取共通部分,還可以用超前掃描
用超前掃描來(lái)分析上述規(guī)則,讀取“恰好 n 個(gè)”token 是行不通的.原因在于共通部分 storage() type() <IDENTIFIER>中存在非終端符號(hào)storage()和type().因?yàn)椴恢?storage() 和 type() 實(shí)際對(duì)應(yīng)幾個(gè) token，所以無(wú)法用讀取“恰好 n 個(gè)”token 來(lái)處理

使用超前掃描的做法

definition(): {}
  {
        LOOKAHEAD(storage() type() <IDENTIFIER> ";")
storage() type() <IDENTIFIER> ";"
| storage() type() <IDENTIFIER> arg_decls() block() 以下省略

超前掃描的相關(guān)注意事項(xiàng)

即便寫(xiě)了 LOOKAHEAD 也并非一定能按照預(yù)期對(duì)程序進(jìn)行分析。添加 LOOKAHEAD 后 Choice conflict 的警告消息的確消失了,不會(huì)對(duì) LOOKAHEAD 描述的內(nèi)容進(jìn)行任何檢查.在發(fā)生選擇沖突的地方加上 LOOKAHEAD 后不再顯示警告,僅此而已. LOOKAHEAD 處理的描述是否正確,我們必須自己思考

語(yǔ)法分析

語(yǔ)法單位

一般編程語(yǔ)言的語(yǔ)法單位有下面這些

定義(definition)
聲明(declaration)
語(yǔ)句(statement)
表達(dá)式(expression)
項(xiàng)(term)

對(duì)以下語(yǔ)法的聲明進(jìn)行了介紹,主要是通過(guò)正則表達(dá)的一些符號(hào),終端符和非終端符的組合,使得對(duì)某些語(yǔ)法的定義符合實(shí)際使用的需求場(chǎng)景,并且避免在各種情況下出現(xiàn)的邏輯漏洞,較為細(xì)節(jié)

import聲明的語(yǔ)法
各類(lèi)定義的語(yǔ)法
變量定義的語(yǔ)法
函數(shù)定義的語(yǔ)法
結(jié)構(gòu)體定義和聯(lián)合體定義的語(yǔ)法

結(jié)構(gòu)體 defstruct 的規(guī)則
defstruct(): {}
{
<STRUCT> name() member_list() ";"
}

聯(lián)合體
defunion(): {}
{
<UNION> name() member_list() ";"
}

結(jié)構(gòu)體成員和聯(lián)合體成員的語(yǔ)法
typedef語(yǔ)句的語(yǔ)法
類(lèi)型的語(yǔ)法 type 和 typeref
基本類(lèi)型的語(yǔ)法

語(yǔ)句的分析

語(yǔ)句的語(yǔ)法

以stmts為例

stmts(): {} {
  (stmt())*
 }

stmt(): {} {
  ( ";"
  | LOOKAHEAD(2) labeled_stmt() | expr() ";"
  | block()
  | if_stmt()
  | while_stmt()
  | dowhile_stmt()
  | for_stmt()
  | switch_stmt()
  | break_stmt()
  | continue_stmt()
  | goto_stmt()
  | return_stmt()
  )
}

if語(yǔ)句的語(yǔ)法
省略if語(yǔ)句和大括號(hào)
while語(yǔ)句的語(yǔ)法
for語(yǔ)句的語(yǔ)法
各類(lèi)跳轉(zhuǎn)語(yǔ)句的語(yǔ)法

表示 break 語(yǔ)句的 break_stmt() 和表示
return 語(yǔ)句的 return_stmt()

表達(dá)式的分析

表達(dá)式的整體結(jié)構(gòu)

一般來(lái)說(shuō)，越是離語(yǔ)法樹(shù)的根節(jié)點(diǎn)近的符號(hào)，其解析規(guī)則越是先出現(xiàn)。這里的“先”是指，從 compilation_unit() 跟蹤調(diào)查規(guī)則時(shí)，會(huì)較早地出現(xiàn)在跟蹤到的規(guī)則中。

表達(dá)式的語(yǔ)法樹(shù)

換言之，就是可以從優(yōu)先級(jí)低的運(yùn)算符的規(guī)則開(kāi)始，按照自上而下的順序來(lái)描述表達(dá)式的規(guī)則。

expr的規(guī)則

expr(): {} {
       LOOKAHEAD(term() "=")
       term() "=" expr()
      | LOOKAHEAD(term() opassign_op())
       term() opassign_op() expr()
      | expr10()
}

這個(gè)規(guī)則比較難以理解，我們姑且如下所示把 LOOKAHEAD 去掉。

 term() "=" rhs_expr()            // 選項(xiàng)1
| term() opassign_op() expr()     // 選項(xiàng)2
| expr10()                        // 選項(xiàng)3

此時(shí)，選項(xiàng) 1 是通的賦值表達(dá)式，選項(xiàng) 2 表示的是自我賦值的表達(dá)式，選項(xiàng) 3 的 expr10() 是比賦值表達(dá)式優(yōu)先級(jí)更高的表達(dá)式。像這樣在 expr 后添加數(shù)字的符號(hào)有 expr1() 到 expr10()。數(shù)字越小，所對(duì)應(yīng)的表達(dá)式的優(yōu)先級(jí)越高

二元運(yùn)算符

opassign_op(): {}
  {
      ( "+="
      | "-="
      | "*="
      | "/="
      | "%="
      | "&="
      | "|="
      | "^="
      | "<<="
      | ">>="
      )
}

條件表達(dá)式

接著來(lái)看一下 expr10() 的規(guī)則。這是條件運(yùn)算符(三元運(yùn)算符)的規(guī)則

expr10(): {}
   {
       expr9() ["?" expr() ":" expr10()]
   }

非終端符號(hào) exprN 中的“N”部分是與優(yōu)先級(jí)對(duì)應(yīng)的，數(shù)值越小優(yōu)先級(jí)越高。上述規(guī)則的優(yōu)先級(jí)為 10，所以屬于較低的優(yōu)先級(jí)。
條件表達(dá)式中有 3 個(gè)表達(dá)式，各個(gè)表達(dá)式分別用哪個(gè) expr 是這里的難點(diǎn)。原則上來(lái)說(shuō) “只要是該處允許的語(yǔ)法所對(duì)應(yīng)的符號(hào)就可以”，但至少對(duì)于最左側(cè)的 expr 有著特別的限制，
那就是“不允許 expr10 自身或開(kāi)頭和 expr10 相匹配的符號(hào)”。
JavaCC 會(huì)將 1 個(gè)規(guī)則轉(zhuǎn)化為 1 個(gè)方法，即如果像上面這樣定義了符號(hào) expr10 的規(guī)則，就
會(huì)生成 expr10 方法，并且會(huì)根據(jù)規(guī)則生成方法的處理內(nèi)容。如果在規(guī)則中寫(xiě)有非終端符號(hào)，就會(huì)直接調(diào)用符號(hào)所對(duì)應(yīng)的方法。也就是說(shuō)，像上面這樣寫(xiě)有 expr9() 的話(huà)，就會(huì)在該處調(diào) 用 expr9 方法。如果寫(xiě)的是終端符號(hào)，則直接轉(zhuǎn)化為 token。
那么如果在 expr10 的定義中又出現(xiàn)了 expr10 的話(huà)會(huì)怎么樣呢?這樣就相當(dāng)于在方法 expr10 中又調(diào)用了 expr10 自身，會(huì)陷入無(wú)限的遞歸之中。所以在 expr10 規(guī)則的左側(cè)不能出現(xiàn) expr10 自身或者以 expr10 開(kāi)頭的符號(hào)。

二元運(yùn)算符

二元運(yùn)算符的優(yōu)先級(jí)

項(xiàng)的分析

項(xiàng)的規(guī)則

term(): {} {
       LOOKAHEAD("(" type()) "(" type() ")" term()
      | unary()
}

需要關(guān)注的細(xì)節(jié)有

前置運(yùn)算符的規(guī)則
后置運(yùn)算符的規(guī)則
字面量的規(guī)則

總結(jié)

總結(jié):該篇較為細(xì)致(瑣碎)的介紹了詞法分析和語(yǔ)法分析的細(xì)節(jié),對(duì)于終端符和非終端符的組合使用,以及在使用中容易遇到的錯(cuò)誤進(jìn)行了非常細(xì)致的舉例說(shuō)明,通過(guò)學(xué)習(xí),需要掌握的有: 超前掃描的使用(很重要,是理解各種組合規(guī)則的基礎(chǔ)), 各種運(yùn)算法則(連接,選擇,忽略,重復(fù)等).

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

編譯器學(xué)習(xí)之 (二) : 詞法分析和語(yǔ)法分析

編譯器學(xué)習(xí)之 (二) : 詞法分析和語(yǔ)法分析

前言

詞法分析

基于EBNF的語(yǔ)法描述

語(yǔ)法的二義性和token的超前掃描

空懸else

選擇沖突

token的超前掃描

可以省略的規(guī)則和沖突

重復(fù)和沖突

更靈活的超前掃描

超前掃描的相關(guān)注意事項(xiàng)

語(yǔ)法分析

語(yǔ)法單位

語(yǔ)句的分析

語(yǔ)句的語(yǔ)法

表達(dá)式的分析

表達(dá)式的整體結(jié)構(gòu)

expr的規(guī)則

條件表達(dá)式

二元運(yùn)算符

項(xiàng)的分析

項(xiàng)的規(guī)則

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

編譯器學(xué)習(xí)之 (二) : 詞法分析和語(yǔ)法分析

前言

詞法分析

基于EBNF的語(yǔ)法描述

語(yǔ)法的二義性和token的超前掃描

空懸else

選擇沖突

token的超前掃描

可以省略的規(guī)則和沖突

重復(fù)和沖突

更靈活的超前掃描

超前掃描的相關(guān)注意事項(xiàng)

語(yǔ)法分析

語(yǔ)法單位

語(yǔ)句的分析

語(yǔ)句的語(yǔ)法

表達(dá)式的分析

表達(dá)式的整體結(jié)構(gòu)

expr的規(guī)則

條件表達(dá)式

二元運(yùn)算符

項(xiàng)的分析

項(xiàng)的規(guī)則

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av