操屁眼的视频在线免费看,日本在线综合一区二区,久久在线观看免费视频,欧美日韩精品久久综

原題 | The of pgen

作者 | Guido van （之父）

譯者 | 豌豆花下貓

原文 |

David 在 US PyCon 2018 上的演講，關(guān)于語(yǔ)法分析生成器（ ），提醒了我應(yīng)該寫(xiě)一下關(guān)于它的歷史。這是一個(gè)簡(jiǎn)短的腦轉(zhuǎn)儲(chǔ)（也許我今后會(huì)解釋它）。

（譯注：我大膽揣測(cè)一下“腦轉(zhuǎn)儲(chǔ)”吧，應(yīng)該說(shuō)的是，把個(gè)人的記憶以及 的歷史細(xì)節(jié)，轉(zhuǎn)化成文字，這是個(gè)存儲(chǔ)固化的過(guò)程，方便傳承。而我做的翻譯工作，就是把這份文檔財(cái)富，普及給更多的 愛(ài)好者。）

實(shí)際上，有兩個(gè) pgen，一個(gè)是最初的，用 C 語(yǔ)言寫(xiě)的，還有一個(gè)則是用 重寫(xiě)的，在 /pgen2 下面。

兩個(gè)都是我寫(xiě)的。最早那個(gè)實(shí)際上是我為 編寫(xiě)的第一份代碼。盡管從技術(shù)上講，我必須首先編寫(xiě)詞法分析程序（lexer）（pgen 和 共用詞法分析程序，但 pgen 對(duì)大多數(shù)標(biāo)記符不起作用）。

之所以我要寫(xiě)自己的語(yǔ)法分析生成器，原因是當(dāng)時(shí)這玩意（我熟悉的）相當(dāng)稀少——基本上就是用 Yacc（有個(gè) GNU 的重寫(xiě)版，叫作 Bison（譯注：美洲野牛），但我不確定那時(shí)的自己是否知道）；或者是自己手寫(xiě)一個(gè)（這是大多數(shù)人所做的）。

我曾在大學(xué)里用過(guò) Yacc，從“龍書(shū)”中熟悉了它的工作原理，但是出于某些原因，我并不喜歡它；IIRC 關(guān)于 LALR(1) 語(yǔ)法的局限性，我很難解釋清楚。

（譯注：1、龍書(shū)，原文是 book，指代《: , , and Tools》，這是一本講編譯原理的書(shū)，屬于編譯原理界的殿堂級(jí)存在。另外還有兩本經(jīng)典著作，稱(chēng)號(hào)分別是“虎書(shū)”、“鯨書(shū)”，三者常常一起出現(xiàn)。2、IIRC，If I ，如果我沒(méi)記錯(cuò)。）

集齊三書(shū)，可以召喚神龍？

我也熟悉 LL(1) 解析器，并已認(rèn)真地編寫(xiě)過(guò)一些遞歸下降的 LL(1) 解析器——我很喜歡它，而且還熟悉 LL(1) 解析器的生成技術(shù)（同樣是因?yàn)辇垥?shū)），所以我有了一個(gè)改進(jìn)念頭想要試驗(yàn)下：使用正則表達(dá)式（某種程度的）而不是標(biāo)準(zhǔn)的 BNF 格式。

龍書(shū)還教會(huì)了我如何將正則表達(dá)式轉(zhuǎn)換成 DFA，所以我把所有這些東西一結(jié)合，pgen 就誕生了。【更新：請(qǐng)參閱下文，對(duì)于這個(gè)理由，有個(gè)略微不同的版本。】

我曾不熟悉更高級(jí)的技術(shù)，或者曾認(rèn)為它們效率太低。（在當(dāng)時(shí)，我覺(jué)得工作在解析器上的大多數(shù)人都是這樣。）

至于詞法分析器（lexer），我決定不使用生成器——我對(duì) Lex 的評(píng)價(jià)要比 Yacc 低得多詞法分析器輸入的是，因?yàn)樵趪L試掃描超過(guò) 255 個(gè)字節(jié)的標(biāo)記符時(shí)，我所熟悉的 Lex 版本會(huì)發(fā)生段錯(cuò)誤（真實(shí)的！）。此外，我認(rèn)為縮進(jìn)格式很難教給詞法分析器生成器。

（譯注：1、這里的生成器并非 語(yǔ)法中的生成器，而是指用來(lái)生成分析器的工具。Lex 是“ ”的簡(jiǎn)稱(chēng)，用來(lái)生成詞法分析器；Yacc 是“Yet ”的簡(jiǎn)稱(chēng)，用來(lái)生成語(yǔ)法分析器。2、段錯(cuò)誤，原文是 ，全稱(chēng)是 fault，指的是因?yàn)樵浇缭L(fǎng)問(wèn)內(nèi)存空間而導(dǎo)致的報(bào)錯(cuò)。）

pgen2 的故事則完全不同。

我曾受雇于 San Mateo 的一家創(chuàng)業(yè)公司（即 ，倒閉于 2007，之后我離開(kāi)并加入了 ），在那我有一項(xiàng)設(shè)計(jì)定制語(yǔ)言的任務(wù)（目標(biāo)是作關(guān)于系統(tǒng)配置的安全性判定），并擁有相當(dāng)大的自主權(quán)。

我決定設(shè)計(jì)一些稍微像 的東西，用 來(lái)實(shí)現(xiàn)，并且決定要重用 pgen，但是后端要基于 ，使用 .py 作為詞法分析器。所以我用 重寫(xiě)了 pgen 里的那些算法，然后繼續(xù)構(gòu)建了剩余的部分。

管理層覺(jué)得把工具開(kāi)源是有意義的，因此他們很快就批準(zhǔn)了，而在不久之后（我當(dāng)時(shí)很可能已經(jīng)轉(zhuǎn)移到 了？），這工具對(duì)于 2to3 也是有意義的。（因?yàn)檩斎敫袷礁嫉?pgen 相同，用它來(lái)生成一個(gè) 解析器很容易——我只需將語(yǔ)法文件喂給工具。:-)

更新：創(chuàng)建 pgen 的原因，還有更多故事

我不完全記得為什么要這樣做了，但我剛偷看了#，我可能覺(jué)得這是一種新的（對(duì)我而言）不通過(guò)添加幫助性的規(guī)則而解決沖突的方式。

例如，該網(wǎng)頁(yè)所稱(chēng)的的左分解（將 A -> X | X Y Z 替換成 A -> X B; B -> Y Z | ），我會(huì)重寫(xiě)成 A -> X [Y Z]。

如果我沒(méi)記錯(cuò)，通過(guò)“正則表達(dá)式 -> NFA -> DFA”的轉(zhuǎn)換過(guò)程，解析引擎（該網(wǎng)頁(yè)中前面的 函數(shù)）依然可以工作在由這些規(guī)則所派生的解析表上；我認(rèn)為這里需要有不出現(xiàn)空白產(chǎn)物的訴求。（譯注：“空白產(chǎn)物”，原文是 empty ，對(duì)應(yīng)的是前文的 ，指的是不必要出現(xiàn) empty。）

我還想起一點(diǎn)，由解析引擎生成的解析樹(shù)節(jié)點(diǎn)可能有很多子節(jié)點(diǎn)，例如，對(duì)于上面的規(guī)則 A -> X [Y Z]，節(jié)點(diǎn) A 可能有 1 個(gè)子節(jié)點(diǎn)（X）或者 3 個(gè)（X Y Z）。代碼生成器中就需要有一個(gè)簡(jiǎn)單的檢查，來(lái)確定它遇到的是哪一種可能的情況。（這已經(jīng)被證明是一把雙刃劍，后來(lái)我們添加了一個(gè)由單獨(dú)的生成器所驅(qū)動(dòng)的“解析樹(shù) -> AST”步驟，以簡(jiǎn)化字節(jié)碼生成器。）

所以我使用正則表達(dá)式的原因，很可能是為了使語(yǔ)法更易于閱讀：在使用了必要的重寫(xiě)以解決沖突之后，我發(fā)現(xiàn)語(yǔ)法不是那么可讀（此處應(yīng)插入《 之禪》的說(shuō)法 :-) ，而正則表達(dá)式則更符合我對(duì)于經(jīng)典語(yǔ)言的語(yǔ)法的看法（除了起著奇怪名字的幫助規(guī)則、[] 部分以及 * 號(hào)重復(fù)的部分）。

正則表達(dá)式?jīng)]有提高 LL(1) 的能力，更沒(méi)有降低它的能力。當(dāng)然了，所謂“正則表達(dá)式”，我想說(shuō)的其實(shí)是 EBNF ——我不確定 “EBNF” 在當(dāng)時(shí)是否是一個(gè)被明確定義了的符號(hào)，它可能就指對(duì) BNF 的任意擴(kuò)展。

假如將 EBNF 轉(zhuǎn)換為 BNF，再去使用它，將會(huì)導(dǎo)致尷尬的多解析樹(shù)節(jié)點(diǎn)問(wèn)題，所以我不認(rèn)為這會(huì)是一種改進(jìn)。

如果讓我重做一遍，我可能會(huì)選擇一個(gè)更強(qiáng)大的解析引擎，可能是 LALR(1) 的某個(gè)版本（例如 Yacc/Bison）。LALR(1) 的某些地方要比 LL(1) 更給力，也更加有用，例如，關(guān)鍵字參數(shù)。

在 LL(1) 中，規(guī)則 “arg: [NAME =] expr” 無(wú)效，因?yàn)?NAME 出現(xiàn)在了表達(dá)式的第一組里（FIRST-set），而 LL(1) 算法沒(méi)法處理這樣的寫(xiě)法。

如果我沒(méi)記錯(cuò)，LALR(1) 則可以處理它。但是，在我寫(xiě)完 pgen 的第一個(gè)版本的好些年之后，關(guān)鍵字參數(shù)寫(xiě)法才出現(xiàn)，那時(shí)候我已不想重做解析器了。

2019 年 3 月更新： 3.8 將刪除 pgen 的 C 版本詞法分析器輸入的是，轉(zhuǎn)而使用重寫(xiě)的 pgen2 版本。參閱

（譯注：感覺(jué)可以幫 Guido 再加一條“更新”了，目前他正在研究 PEG 解析器，將會(huì)作為 pgen 的替代。）

▼ 點(diǎn)擊成為社區(qū)注冊(cè)會(huì)員 「在看」一下，一起PY！