原題 | Visualizing PEG Parsing

作者 | Guido van Rossum（Python之父）

譯者 | 豌豆花下貓（“Python貓”公眾號作者）

聲明 | 本翻譯是出于交流學習的目的，基于 CC BY-NC-SA 4.0 授權協議。為便于閱讀，內容略有改動。

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

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

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

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

閱讀此圖表時，要注意的主要事項是：頂部和底部部分的縮進線與標記符緩沖區相對應。（譯注：最好看一下后面的 gif 動圖，再往下看這部分內容。）

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

緩存部分的條目的縮進也對應著標記符緩沖區的位置。例如，在底部，我們看到有負數緩存條目（negative cache entries）在標記符緩沖區的開頭查找標記符 'if' 以及規則 if_statement 。我們還發現標記符 '=' 和 NAME （特別是 'cat' ）所成功緩存的條目，它們與將來的輸入位置相對應。

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

（說到“跳躍”，頂部顯示的解析器堆棧會在一個調用被添加到堆棧時，向上移動，而當從堆棧中彈出一個調用時，它則向下移動。似乎我們的眼睛跟隨這樣的動作不會有太大問題——至少我沒有。這很可能因為我們大腦中有一塊區域是用于跟蹤移動的物體。:-)

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

讓我們看一下解析堆棧在顯示時的更多一些細節。前四個條目對應于尚未返回的解析方法，每一行顯示了語法中的一行。帶下劃線的條目會引起下一次調用。

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

在那之后，我們看到導致第二個選項（ atom '/' term ）失敗的結果： expect（'/'） - > None 用 '+' 標記符縮進。當我們將可視化向前移動時，我們會看到它沉入緩存中。

但當然了，你肯定寧愿自己看動畫！我已經錄制了示例程序的完整解析。你也可以自己玩代碼，但請注意，這只是一個臨時的黑科技。

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

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

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

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

標記符緩沖區中的光標向左跳躍，顯示了回溯過程；該動圖中有很多次出現這種現象。你還可以在 gif 中觀察到緩存填充，解析器在那不會進行額外的遞歸調用。（發現這種情況時，我應該加以強調，但我沒時間了。）

下周我將進一步開發解析器，很可能會添加我對左遞歸語法規則的實現。（它們很棒！）

致謝：錄制時所用的 ttygif （Ilia Choly 開發） 和 ttyrec （Matthew Jording 開發）。

本文內容、示例代碼和圖片的授權協議：CC BY-NC-SA 4.0

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

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

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

公眾號【 Python貓 】， 本號連載優質的系列文章，有喵星哲學貓系列、Python進階系列、好書推薦系列、技術寫作、優質英文推薦與翻譯等等，歡迎關注哦。