原題 | Visualizing PEG Parsing

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號(hào)作者）

聲明 | 本翻譯是出于交流學(xué)習(xí)的目的，基于 CC BY-NC-SA 4.0 授權(quán)協(xié)議。為便于閱讀，內(nèi)容略有改動(dòng)。

上周我展示了一個(gè)簡單的 PEG 解析器生成器。本周我將展示生成的解析器在解析程序時(shí)實(shí)際執(zhí)行的操作。我深入研究了 ASCII 藝術(shù)的復(fù)古世界，特別是一個(gè)名為“curses”的庫，它可以在 Linux 和 Mac 的 Python 標(biāo)準(zhǔn)庫中找到，也可以作為 Windows 的附加組件。

【這是我的 PEG 系列的第 4 部分。見第1部分，第2部分，第3部分，第5部分 】（譯注：對(duì)應(yīng)的譯文，第1篇、第2篇、第3篇、第5篇待譯 ）

讓我們來看看可視化已取得的進(jìn)展。截圖里的屏幕被分隔為三個(gè)部分，分別是簡單的 ASCII 字符，以及用連字符劃出的線：

• 上部分顯示了解析器的調(diào)用堆棧，你可能還記得它是一個(gè)具有無限回溯的遞歸下降解析器。我將在下面解釋如何閱讀它。
• 中間的單行部分展示了標(biāo)記符緩沖區(qū)的內(nèi)容，光標(biāo)指向下一個(gè)要解析的標(biāo)記符。
• 在底部，我們呈現(xiàn) packrat 解析算法使用的記憶緩存。它的條目類似于一些解析器堆棧條目（具有結(jié)果的條目）。

閱讀此圖表時(shí)，要注意的主要事項(xiàng)是：頂部和底部部分的縮進(jìn)線與標(biāo)記符緩沖區(qū)相對(duì)應(yīng)。（譯注：最好看一下后面的 gif 動(dòng)圖，再往下看這部分內(nèi)容。）

• 前兩行（以 statement 和 assignment 開頭）表示尚未返回的解析方法調(diào)用，并且當(dāng)標(biāo)記位置處在第一個(gè)標(biāo)記符（'aap' ）之前時(shí)調(diào)用。
• 接下來的兩行（以 expr 和 term 開頭）與標(biāo)記符 'cat' 的開頭垂直對(duì)齊，后者是調(diào)用相應(yīng)解析方法的地方。
• 堆棧部分所顯示的第五行和最后一行是一個(gè) expect('/') 調(diào)用，它返回 None 。它是在標(biāo)記符 '+' 處被調(diào)用的。

緩存部分的條目的縮進(jìn)也對(duì)應(yīng)著標(biāo)記符緩沖區(qū)的位置。例如，在底部，我們看到有負(fù)數(shù)緩存條目（negative cache entries）在標(biāo)記符緩沖區(qū)的開頭查找標(biāo)記符 'if' 以及規(guī)則 if_statement 。我們還發(fā)現(xiàn)標(biāo)記符 '=' 和 NAME （特別是 'cat' ）所成功緩存的條目，它們與將來的輸入位置相對(duì)應(yīng)。

在顯示出來的解析器堆棧和緩存中，已返回的調(diào)用被顯示成 function(args) -> result 。有時(shí)解析器堆棧也會(huì)顯示幾個(gè)已返回的方法——我這樣做是為了減少顯示時(shí)的“跳躍性”。

（說到“跳躍”，頂部顯示的解析器堆棧會(huì)在一個(gè)調(diào)用被添加到堆棧時(shí)，向上移動(dòng)，而當(dāng)從堆棧中彈出一個(gè)調(diào)用時(shí)，它則向下移動(dòng)。似乎我們的眼睛跟隨這樣的動(dòng)作不會(huì)有太大問題——至少我沒有。這很可能因?yàn)槲覀兇竽X中有一塊區(qū)域是用于跟蹤移動(dòng)的物體。:-)

緩存被可視化為一種 LRU 緩存，最近使用過的緩存條目位于頂部，較少使用的項(xiàng)目則向屏幕底部掉落。（我在之前的帖子中展示的 packrat 解析器原型不使用 LRU，但它可能是改善其內(nèi)存使用的好策略。）

讓我們看一下解析堆棧在顯示時(shí)的更多一些細(xì)節(jié)。前四個(gè)條目對(duì)應(yīng)于尚未返回的解析方法，每一行顯示了語法中的一行。帶下劃線的條目會(huì)引起下一次調(diào)用。

在這種情況下，我們看到我們處于 statement 的第二種選擇，也即 assignment，并且在該規(guī)則中我們處于第三項(xiàng)，即 expr。在 expr 規(guī)則中，我們只是在第一個(gè)可選項(xiàng)的第一個(gè)條目（ term '+' expr ）；而在 term 規(guī)則中，我們處在最后的選項(xiàng)（ atom ）。

在那之后，我們看到導(dǎo)致第二個(gè)選項(xiàng)（ atom '/' term ）失敗的結(jié)果： expect（'/'） - > None 用 '+' 標(biāo)記符縮進(jìn)。當(dāng)我們將可視化向前移動(dòng)時(shí)，我們會(huì)看到它沉入緩存中。

但當(dāng)然了，你肯定寧愿自己看動(dòng)畫！我已經(jīng)錄制了示例程序的完整解析。你也可以自己玩代碼，但請(qǐng)注意，這只是一個(gè)臨時(shí)的黑科技。

gif圖：https://raw.githubusercontent.com/gvanrossum/pegen/master/story3/tty.gif

示例代碼：https://github.com/gvanrossum/pegen/tree/master/story3

當(dāng)你在觀看錄制的GIF時(shí)，可能會(huì)感到有些迷惑，有時(shí)下一個(gè)標(biāo)記符還未顯示（例如，在最開始時(shí)，堆棧在標(biāo)記符 'aap' 被顯示之前，就增長了幾個(gè)條目）。

這正是解析器所看到的：標(biāo)記符緩沖區(qū)被延遲地填充，并且在解析器通過調(diào)用 expect() 來請(qǐng)求它們之前，并不會(huì)掃描標(biāo)記符。一旦標(biāo)記符出現(xiàn)在緩沖區(qū)中，它就會(huì)保留在那里，即便在解析器回溯時(shí)也如此。

標(biāo)記符緩沖區(qū)中的光標(biāo)向左跳躍，顯示了回溯過程；該動(dòng)圖中有很多次出現(xiàn)這種現(xiàn)象。你還可以在 gif 中觀察到緩存填充，解析器在那不會(huì)進(jìn)行額外的遞歸調(diào)用。（發(fā)現(xiàn)這種情況時(shí)，我應(yīng)該加以強(qiáng)調(diào)，但我沒時(shí)間了。）

下周我將進(jìn)一步開發(fā)解析器，很可能會(huì)添加我對(duì)左遞歸語法規(guī)則的實(shí)現(xiàn)。（它們很棒！）

致謝：錄制時(shí)所用的 ttygif （Ilia Choly 開發(fā)） 和 ttyrec （Matthew Jording 開發(fā)）。

本文內(nèi)容、示例代碼和圖片的授權(quán)協(xié)議：CC BY-NC-SA 4.0

英文原文：https://medium.com/@gvanrossum_83706/visualizing-peg-parsing-93a36f259423

作者簡介： Guido van Rossum，Python 的創(chuàng)造者，一直是“終身仁慈獨(dú)裁者”，直到 2018 年 7 月 12 日退位。目前，他是新的最高決策層的五位成員之一，依然活躍在社區(qū)中。本文出自他在 Medium 開博客所寫的解析器系列，該系列仍在連載中，每周日更新。

譯者簡介： 豌豆花下貓，生于廣東畢業(yè)于武大，現(xiàn)為蘇漂程序員，有一些極客思維，也有一些人文情懷，有一些溫度，還有一些態(tài)度。公眾號(hào)：「Python貓」（python_cat）。

公眾號(hào)【 Python貓 】， 本號(hào)連載優(yōu)質(zhì)的系列文章，有喵星哲學(xué)貓系列、Python進(jìn)階系列、好書推薦系列、技術(shù)寫作、優(yōu)質(zhì)英文推薦與翻譯等等，歡迎關(guān)注哦。