PLY (Python Lex-Yacc)

文章目錄

• • 1. Preface and Requirements
  • 2. Introduction
  • 3. PLY Overview
  • 4. Lex
  • • 4.1 Lex Example
    • 4.2 The tokens list
    • 4.3 Specification of tokens
    • 4.4 Token values
    • 4.5 Discarded tokens
    • 4.6 Line numbers and positional information
    • 4.7 Ignored characters
    • 4.8 Literal characters
    • 4.9 Error handling
    • 4.10 EOF Handling
    • 4.11 Building and using the lexer
    • 4.12 The @TOKEN decorator
    • 4.13 Optimized mode
    • 4.14 Debugging
    • 4.15 Alternative specification of lexers
    • 4.16 Maintaining state
    • 4.17 Lexer cloning
    • 4.18 Internal lexer state
    • 4.19 Conditional lexing and start conditions
    • 4.20 Miscellaneous Issues
  • 5. Parsing basics
  • 6. Yacc
  • • 6.1 An example
    • 6.2 Combining Grammar Rule Functions
    • 6.3 Character Literals
    • 6.4 Empty Productions
    • 6.5 Changing the starting symbol
    • 6.6 Dealing With Ambiguous Grammars
    • 6.7 The parser.out file
    • 6.8 Syntax Error Handling
    • 6.9 Line Number and Position Tracking
    • 6.10 AST Construction
    • 6.11 Embedded Actions
    • 6.12 Miscellaneous Yacc Notes
  • 7. Multiple Parsers and Lexers
  • 8. Using Python's Optimized Mode
  • 9. Advanced Debugging
  • • 9.1 Debugging the lex() and yacc() commands
    • 9.2 Run-time Debugging
  • 10. Packaging Advice
  • 11. Where to go from here?

1. Preface and Requirements

本文檔提供了使用PLY進行詞法分析和解析的概述，考慮到解析的內在復雜性，我強烈建議您在使用PLY進行大型開發項目之前閱讀(或至少略讀)整個文檔。

2. Introduction

PLY是流行的編譯器構造工具lex和yacc的純python實現。PLY的主要目標是相當忠實于傳統lex/yacc工具的工作方式。這包括支持LALR(1)解析，以及提供廣泛的輸入驗證、錯誤報告和診斷。因此，如果您在另一種編程語言中使用過yacc，那么使用PLY應該相對簡單。

PLY的早期版本是為了支持David 2001年在芝加哥大學(University of Chicago)教授的編譯器入門課程而開發的。由于PLY最初是作為教學工具開發的，所以您會發現它對標記和語法規則規范相當挑剔。在某種程度上，這種附加的形式是為了捕捉新手用戶所犯的常見編程錯誤。然而，高級用戶在為真正的編程語言構建復雜語法時也會發現這些特性非常有用。還應該注意，PLY沒有提供太多額外功能(例如，自動構造抽象語法樹、遍歷樹等)。我也不認為它是一個解析框架。相反，您將發現一個完全用Python編寫的、功能齊全的基本lex/yacc實現。

本文的其余部分需要假設您對解析理論、語法制導翻譯以及其他編程語言中編譯器構造工具(如lex和yacc)的使用有一定的了解。如果您不熟悉這些主題，您可能想要查閱介紹性的文本，例如Aho、Sethi和Ullman編寫的“編譯器:原則、技術和工具”。O’Reilly的John Levine的《Lex and Yacc》可能也很方便。事實上，O’Reilly的書可以作為PLY的參考，因為這兩個概念實際上是相同的。

3. PLY Overview

PLY由兩個單獨的模塊組成:lex.py 和 yacc. p y。都可以在名為ply的Python包中找到。

lex.py模塊用于將輸入的文本通過正則表達式轉化成一系列特定的token。

yacc.py用于識別以上下文無關語法形式指定的語言語法。

這兩種工具應該一起工作。具體來說，lex.py以token()函數的形式提供了一個外部接口，該函數返回輸入流上的下一個有效token。yacc.py用于反復調用函數來檢索標記并調用語法規則。yacc.py的輸出通常是抽象語法樹(AST)。然而，這完全取決于用戶。如果需要，還可以使用yacc.py實現簡單的單遍編譯器。

與Unix對應程序一樣，yacc.py提供了您期望的大部分特性，包括廣泛的錯誤檢查、語法驗證、對空結果的支持、錯誤標記以及通過優先規則解決歧義。事實上，幾乎所有在傳統yacc中可以實現的功能都應該得到充分的支持。

yacc.py和Unix 中yacc的主要區別在于，yacc.py不涉及單獨的代碼生成過程。相反，PLY依賴于反射(內省)來構建它的詞法分析器和解析器。與傳統的lex/yacc不同，傳統的lex/yacc需要將一個特殊的輸入文件轉換為一個單獨的源文件，而PLY的規范是有效的Python程序。

這意味著沒有額外的源文件，也沒有特殊的編譯器構造步驟(例如，運行yacc為編譯器生成Python代碼)。由于生成解析表的成本相對較高，PLY緩存結果并將其保存到文件中。如果在輸入源中沒有檢測到任何更改，則從緩存中讀取表。否則，它們將被重新生成。

4. Lex

lex.py用于將輸入的代碼轉化為token序列，假設你將輸入的程序語言為如下的語句：

x = 3 + 42 * (s - t)

一個分詞器將會把這語句分割成單個的token：

'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'

Token通常需要給一個名字來標注它們是哪個類型的，例如：

'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES','LPAREN','ID','MINUS','ID','RPAREN'

更具體的來講，輸入被分成包含類型和相應值的序列，例如：

('ID','x'), ('EQUALS','='), ('NUMBER','3'), ('PLUS','+'), ('NUMBER','42), ('TIMES','*'),('LPAREN','('), ('ID','s'), ('MINUS','-'),('ID','t'), ('RPAREN',')'

通常情況下通過一系列的正則表達式來確定token，下一節將來具體介紹它在lex.py中如何實現。

4.1 Lex Example

下面的例子將介紹lex.py將如何實現一個簡單的分詞器。

# ------------------------------------------------------------ # calclex.py # # tokenizer for a simple expression evaluator for # numbers and +,-,*,/ # ------------------------------------------------------------ import ply.lex as lex# List of token names. This is always required tokens = ('NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN', )# Regular expression rules for simple tokens t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' t_LPAREN = r'\(' t_RPAREN = r'\)'# A regular expression rule with some action code def t_NUMBER(t):r'\d+'t.value = int(t.value) return t# Define a rule so we can track line numbers def t_newline(t):r'\n+'t.lexer.lineno += len(t.value)# A string containing ignored characters (spaces and tabs) t_ignore = ' \t'# Error handling rule def t_error(t):print("Illegal character '%s'" % t.value[0])t.lexer.skip(1)# Build the lexer lexer = lex.lex()

要想使用這個詞法分析程序，你首先需要使用input()方法輸入一些文本，然后重復調用token()方法生成token序列，如下代碼是展示了它是如何運作的。

# Test it outdata = '''3 + 4 * 10+ -20 *2'''# Give the lexer some inputlexer.input(data)# Tokenizewhile True:tok = lexer.token()if not tok: break # No more inputprint(tok)

執行的結果為：

LexToken(NUMBER,3,2,1)LexToken(PLUS,'+',2,3)LexToken(NUMBER,4,2,5)LexToken(TIMES,'*',2,7)LexToken(NUMBER,10,2,10)LexToken(PLUS,'+',3,14)LexToken(MINUS,'-',3,16)LexToken(NUMBER,20,3,18)LexToken(TIMES,'*',3,20)LexToken(NUMBER,2,3,21)

lexer.token()方法會返回一個LexToken的實例，該對象中的屬性包括：tok.type, tok.value, tok.lineno和tok.lexpos。

其中type和value指的是token中的類型和相應的值，tok.lineno和tok.lexpos表示的這個token的位置，tok.lexpos 是相對應的這段輸入文本起始地址的相對地址。

例如“3”這個數字表示了位于data中第2行，是data第一個元素，“+”（第三行）表示了位于data中第3行，是data第14個元素。注意一個空格也算占一個位置。

4.2 The tokens list

所有的詞法分析程序必須定義tokens來表明所有可能的token名稱，只有這些名稱將會被詞法分析程序來處理。定義這個序列往往是必要的，也被用于執行各種驗證檢查。而且在yacc.py模塊中也用于確定終結符。

例如，下列代碼確定了一系列的token名稱：

tokens = ('NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN',)

4.3 Specification of tokens

每個token都是通過編寫與Python的re模塊兼容的正則表達式規則來指定的。每個規則都是通過使用一個特殊前綴t_聲明來定義的，以表明它定義了一個token。

對于簡單的token，正則表達式可以指定為這樣的字符串(注意:使用Python原始字符串，因為它們是編寫正則表達式字符串最方便的方法):

t_PLUS = r'\+'

在這種情況下，t_后面的名稱必須與tokens中提供的名稱完全匹配。如果需要執行某種操作，可以將令牌規則指定為函數。例如，該規則匹配數字并將字符串轉換為Python整數。

def t_NUMBER(t):r'\d+'t.value = int(t.value)return t

當使用函數時，正則表達式規則在函數文檔字符串中指定。該函數總是接受單個參數，即LexToken的實例。每個LexToken中含有四種屬性：

• t.type ：類型
• t.value：值
• t.lineno ：標明第幾行
• t.lexpos ：相對于文本起始位置的相對位置

通常情況下，t.type的名稱與t_后跟的名稱一致，action函數可以根據需要修改LexToken對象的內容。但是，當它完成時，應該返回生成的token。如果action函數沒有返回值，則只丟棄令牌并讀取下一個token。

在內部，lex.py使用re模塊進行模式匹配。模式是使用re.VERBOSE標志編譯的，該標志可用于提高可讀性。但是，請注意，未轉義的空格將被忽略，并且在此模式下允許注釋。如果您的模式包含空格，請確保使用\s。如果需要匹配#字符，請使用[#]。

構建主正則表達式時，按如下順序添加規則:

1）函數定義的所有token都按照它們在lexer文件中出現的相同順序添加。

2）按照正則表達式長度遞減的順序對字符串定義的標記進行排序(首先添加更長的表達式)。

如果沒有這種排序，就很難正確匹配某些類型的token。例如，如果您想為“=”和“==” 使用單獨的標記，您需要確保首先選中了“==”。通過對正則表達式按長度遞減排序，解決了定義為字符串的規則的排序問題。對于函數，可以顯式地控制順序，因為首先檢查出現的規則。

要處理保留字，您應該編寫一個規則來匹配標識符，并在函數中執行一個特殊的名稱查找，如下所示:

reserved = {'if' : 'IF','then' : 'THEN','else' : 'ELSE','while' : 'WHILE',...}tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values())def t_ID(t):r'[a-zA-Z_][a-zA-Z_0-9]*'t.type = reserved.get(t.value,'ID')# Check for reserved wordsreturn t

這種方法極大地減少了正則表達式規則的數量，并可能使事情更快一些。

注意:您應該避免為保留字編寫單獨的規則。例如，如果你這樣寫規則：

t_FOR = r'for't_PRINT = r'print'

對于包含這些單詞作為前綴的標識符，如“forget”或“printed”，將觸發這些規則。這可能不是你想要的。

4.4 Token values

當lex返回token時，它們有一個值存儲在value屬性中。通常，值是匹配的文本。但是，該值可以分配給任何Python對象。例如，在對標識符進行詞法分析時，可能希望同時返回標識符名稱和來自某種符號表的信息。要做到這一點，你可以這樣寫一條規則:

def t_ID(t):...# Look up symbol table information and return a tuplet.value = (t.value, symbol_lookup(t.value))...return t

需要注意的是，不建議使用其他屬性名存儲數據。yacc.py模塊只公開value屬性的內容。因此，訪問其他屬性可能是不必要的尷尬。如果需要在token上存儲多個值，請將元組、字典或實例賦值。

4.5 Discarded tokens

如果是注釋，則需要跳過對應標志，例如：

def t_COMMENT(t):r'\#.*'pass# No return value. Token discarded

或者，您可以在token聲明中包含前綴“ignore_”，以強制忽略token。例如:

t_ignore_COMMENT = r'\#.*'

請注意，如果忽略了許多不同類型的文本，您可能仍然希望使用函數，因為這些函數提供了對正則表達式匹配順序的更精確控制(即，函數按指定的順序匹配，而字符串按正則表達式長度排序)。

4.6 Line numbers and positional information

默認情況下，lex.py并不知道行號信息，因為它并不清楚是什么構成了一行（例如一個換行符）。如果要更新這個信息，則需要寫一個規則，如：

# Define a rule so we can track line numbersdef t_newline(t):r'\n+'t.lexer.lineno += len(t.value)

在這個規則下，lineno 屬性就會更新了，當這個行號更新以后，這個token就直接被忽略了，而不用返回值。

lex.py沒有使用任何自動的列追蹤，然而它確實在lexpos 中記錄了token相關的位置信息，使用這種方法，通常可以將計算列信息作為一個單獨的步驟。例如，只需向后計數，直到到達換行為止。

# Compute column.# input is the input text string# token is a token instancedef find_column(input, token):line_start = input.rfind('\n', 0, token.lexpos) + 1return (token.lexpos - line_start) + 1

由于列信息通常只在錯誤處理上下文中有用，因此可以在需要時計算列位置，而不是對每個token進行計算。

4.7 Ignored characters

對于輸入流中應該完全忽略的字符，lex.py保留了特殊的t_ignore規則。通常這是用來跳過空白和其他不必要的字符。盡管可以以類似于t_newline()的方式為空白定義正則表達式規則，但是t_ignore的使用提供了更好的詞法分析性能，因為它是作為一種特殊情況處理的，并且以比常規正則表達式規則更有效的方式進行檢查。

當t_ignore中給出的字符是其他正則表達式模式的一部分時，這些字符不會被忽略。例如，如果您有一個捕獲引用文本的規則，那么該模式可以包含被忽略的字符(將以正常方式捕獲這些字符)。t_ignore的主要目的是忽略要解析的標記之間的空格和其他填充。

4.8 Literal characters

文字字符可以通過在詞法分析模塊中定義變量文字來指定。例如:

literals = [ '+','-','*','/' ]

或者：

literals = "+-*/"

文字字符只是lexer遇到時返回“原樣”的單個字符。

在所有定義的正則表達式規則之后檢查文本。因此，如果規則以其中一個文字字符開始，它總是優先。

當返回文字標記時，它的類型和值屬性都設置為字符本身。例如,“+”。

當字面值匹配時，可以編寫執行附加操作的token函數。但是，您需要適當地設置token類型。例如:

literals = [ '{', '}' ]def t_lbrace(t):r'\{'t.type = '{' # Set token type to the expected literalreturn tdef t_rbrace(t):r'\}'t.type = '}' # Set token type to the expected literalreturn t

4.9 Error handling

t_error函數的作用是:處理檢測到非法字符時發生的詞法分析錯誤。

# Error handling ruledef t_error(t):print("Illegal character '%s'" % t.value[0])t.lexer.skip(1)

在本例中，我們只需打印出違規字符并通過調用t.lexer.skip(1)跳過一個字符。

4.10 EOF Handling

t_eof()函數的作用是:處理輸入中的文件結束(EOF)條件。作為輸入，它接收一個token類型“eof”，并適當設置lineno和lexpos屬性。這個函數的主要用途是為lexer提供更多的輸入，以便它能夠繼續解析。下面是一個例子:

# EOF handling ruledef t_eof(t):# Get more input (Example)more = raw_input('... ')if more:self.lexer.input(more)return self.lexer.token()return None

EOF函數應該返回下一個可用的token(通過調用self.lexer.token()或None來指示沒有更多的數據。注意，使用self.lexer.input()方法設置更多的輸入并不會重置lexer狀態或用于位置跟蹤的lineno屬性。lexpos屬性被重置，所以如果在錯誤報告中使用它，請注意這一點。

4.11 Building and using the lexer

構建一個詞法分析器的方法為：

lexer = lex.lex()

該函數使用Python反射(或內省)從調用上下文中讀取正則表達式規則并構建lexer。一旦構建了lexer，就可以使用兩種方法來控制lexer。

• lexer.input(data). 根據輸入的data重新設置詞法分析器
• lexer.token(). 返回下一個token。

4.12 The @TOKEN decorator

在某些應用程序中，您可能希望將構建token定義為一系列更復雜的正則表達式規則。例如:

digit = r'([0-9])'nondigit = r'([_A-Za-z])'identifier = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)' def t_ID(t):# want docstring to be identifier above. ?????...

在本例中，我們希望ID的正則表達式規則是上面的變量之一。但是，無法使用普通的文檔字符串直接指定它。要解決這個問題，可以使用@TOKEN裝飾器。例如:

from ply.lex import TOKEN@TOKEN(identifier)def t_ID(t):...

這將為t_ID()附加標識符，允許lex.py正常工作。

4.13 Optimized mode

為了提高性能，最好使用Python的優化模式(例如，使用-O選項運行Python)。但是，這樣做會導致Python忽略文檔字符串。這給lex.py帶來了特殊的問題。要處理這種情況，可以使用如下優化選項創建lexer:

lexer = lex.lex(optimize=1)

接下來，以正常的操作模式運行Python。當您這樣做時，lex.py將在包含lexer規范的模塊所在的目錄中編寫一個名為lextab.py的文件。該文件包含在詞法分析期間使用的所有正則表達式規則和表。在隨后的執行中，只需要導入lextab.py來構建lexer。這種方法大大提高了lexer的啟動時間，并且可以在Python的優化模式下工作。

要更改lexer生成的模塊的名稱，請使用lextab關鍵字參數。例如:

lexer = lex.lex(optimize=1,lextab="footab")

在優化模式下運行時，必須注意lex禁用了大多數錯誤檢查。因此，只有在您確信所有操作都是正確的，并且準備好開始發布生產代碼時，才真正推薦這樣做。

4.14 Debugging

為了調試，您可以在調試模式下運行lex()，如下所示:

lexer = lex.lex(debug=1)

這將生成各種調試信息，包括所有添加的規則、lexer使用的主正則表達式和詞法分析期間生成的標記。

此外，lex.py附帶了一個簡單的main函數，它可以標記從標準輸入讀取的輸入，也可以標記從命令行指定的文件讀取的輸入。要使用它，只需把它放進你的詞典:

if __name__ == '__main__':lex.runmain()

有關調試的更高級細節，請參閱末尾的“調試”一節。

4.15 Alternative specification of lexers

如示例所示，lexer都是在一個Python模塊中指定的。如果希望將token規則放在與調用lex()的模塊不同的模塊中，請使用module關鍵字參數。

例如，您可能有一個專門的模塊，它只包含token規則:

# This module just contains the lexing rules# List of token names. This is always required tokens = ('NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN', )# Regular expression rules for simple tokens t_PLUS = r'\+' t_MINUS = r'-' t_TIMES = r'\*' t_DIVIDE = r'/' t_LPAREN = r'\(' t_RPAREN = r'\)'# A regular expression rule with some action code def t_NUMBER(t):r'\d+'t.value = int(t.value) return t# Define a rule so we can track line numbers def t_newline(t):r'\n+'t.lexer.lineno += len(t.value)# A string containing ignored characters (spaces and tabs) t_ignore = ' \t'# Error handling rule def t_error(t):print("Illegal character '%s'" % t.value[0])t.lexer.skip(1)

使用這個token規則的代碼如下：

>>> import tokrules>>> lexer = lex.lex(module=tokrules)>>> lexer.input("3 + 4")>>> lexer.token()LexToken(NUMBER,3,1,1,0)>>> lexer.token()LexToken(PLUS,'+',1,2)>>> lexer.token()LexToken(NUMBER,4,1,4)>>> lexer.token()None

模塊選項還可以用于從類的實例定義lexer。例如:

import ply.lex as lex class MyLexer(object):# List of token names. This is always requiredtokens = ('NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN',)# Regular expression rules for simple tokenst_PLUS = r'\+'t_MINUS = r'-'t_TIMES = r'\*'t_DIVIDE = r'/'t_LPAREN = r'\('t_RPAREN = r'\)'# A regular expression rule with some action code# Note addition of self parameter since we're in a classdef t_NUMBER(self,t):r'\d+'t.value = int(t.value) return t# Define a rule so we can track line numbersdef t_newline(self,t):r'\n+'t.lexer.lineno += len(t.value)# A string containing ignored characters (spaces and tabs)t_ignore = ' \t'# Error handling ruledef t_error(self,t):print("Illegal character '%s'" % t.value[0])t.lexer.skip(1)# Build the lexerdef build(self,**kwargs):self.lexer = lex.lex(module=self, **kwargs)# Test it outputdef test(self,data):self.lexer.input(data)while True:tok = self.lexer.token()if not tok: breakprint(tok)# Build the lexer and try it out m = MyLexer() m.build() # Build the lexer m.test("3 + 4") # Test it

在從類構建lexer時，應該從類的實例而不是類對象本身構建lexer。這是因為PLY只有在lexer操作由綁定方法定義時才能正常工作。

當使用lex()的模塊選項時，PLY使用dir()函數從底層對象收集符號。不能直接訪問作為模塊值提供的對象的_dict__屬性。

最后，如果您希望保持良好的封裝，但不希望使用完整的類定義，可以使用閉包定義lexer。例如:

import ply.lex as lex# List of token names. This is always requiredtokens = ('NUMBER','PLUS','MINUS','TIMES','DIVIDE','LPAREN','RPAREN',)def MyLexer():# Regular expression rules for simple tokenst_PLUS = r'\+'t_MINUS = r'-'t_TIMES = r'\*'t_DIVIDE = r'/'t_LPAREN = r'\('t_RPAREN = r'\)'# A regular expression rule with some action codedef t_NUMBER(t):r'\d+'t.value = int(t.value) return t# Define a rule so we can track line numbersdef t_newline(t):r'\n+'t.lexer.lineno += len(t.value)# A string containing ignored characters (spaces and tabs)t_ignore = ' \t'# Error handling ruledef t_error(t):print("Illegal character '%s'" % t.value[0])t.lexer.skip(1)# Build the lexer from my environment and return it return lex.lex()

重要提示:如果您使用類或閉包定義lexer，請注意PLY仍然要求您僅為每個模塊(源文件)定義一個lexer。如果不遵循這條規則，那么層中有大量的驗證/錯誤檢查部分可能會錯誤地報告錯誤消息。

4.16 Maintaining state

在lexer中，您可能希望維護各種狀態信息。這可能包括模式設置、符號表和其他細節。作為一個例子，假設您想跟蹤遇到了多少個NUMBER 。

一種方法是在創建lexer的模塊中保留一組全局變量。例如:

num_count = 0def t_NUMBER(t):r'\d+'global num_countnum_count += 1t.value = int(t.value) return t

如果您不喜歡使用全局變量，那么可以在lex()創建的Lexer對象中存儲信息。為此，您可以使用傳遞給各種規則的令牌的lexer屬性。例如:

def t_NUMBER(t):r'\d+'t.lexer.num_count += 1 # Note use of lexer attributet.value = int(t.value) return tlexer = lex.lex()lexer.num_count = 0 # Set the initial count

后一種方法的優點是簡單，可以在同一個應用程序中存在多個給定lexer實例的應用程序中正確工作。然而，對于OO純粹主義者來說，這也可能是對封裝的嚴重違反。為了讓您放心，lexer的所有內部屬性(lineno除外)都有以lex為前綴的名稱(例如，lexdata、lexpos等)。因此，在lexer中存儲沒有以該前綴開頭的名稱或與預定義方法(例如input()、token()等)沖突的名稱的屬性是完全安全的。

如果不喜歡對lexer對象賦值，可以將lexer定義為一個類，如下面的部分所示:

class MyLexer:...def t_NUMBER(self,t):r'\d+'self.num_count += 1t.value = int(t.value) return tdef build(self, **kwargs):self.lexer = lex.lex(object=self,**kwargs)def __init__(self):self.num_count = 0

如果您的應用程序要創建同一個lexer的多個實例，并且需要管理大量狀態，那么類方法可能是最容易管理的。

狀態也可以通過閉包來管理。例如，在python3中:

def MyLexer():num_count = 0...def t_NUMBER(t):r'\d+'nonlocal num_countnum_count += 1t.value = int(t.value) return t...

4.17 Lexer cloning

如果需要，可以通過調用它的clone()方法復制lexer對象。例如:

lexer = lex.lex()...newlexer = lexer.clone()

克隆lexer時，該副本與原始lexer完全相同，包括任何輸入文本和內部狀態。但是，克隆允許提供一組不同的輸入文本，這些文本可以單獨處理。在編寫涉及遞歸或可重入處理的解析器/編譯器時，這可能很有用。例如，如果出于某種原因需要提前掃描輸入，可以創建一個克隆并使用它來提前查看。或者，如果您正在實現某種預處理器，可以使用克隆的lexer來處理不同的輸入文件。

創建克隆與調用lex.lex()不同，因為PLY不會重新生成任何內部表或正則表達式。

在克隆還使用類或閉包維護自身內部狀態的lexer時，需要特別注意。也就是說，您需要知道新創建的lexer將與原始lexer共享所有這些狀態。例如，如果您將lexer定義為一個類并執行以下操作:

m = MyLexer()a = lex.lex(object=m) # Create a lexerb = a.clone() # Clone the lexer

然后a和b都將綁定到同一個對象m上，對m的任何更改都將反映在兩個lexer中。需要強調的是，clone()只意味著創建一個新的lexer，它重用另一個lexer的正則表達式和環境。如果需要創建一個全新的lexer副本，那么再次調用lex()。

4.18 Internal lexer state

Lexer對象Lexer具有許多內部屬性，這些屬性在某些情況下可能有用。

lexer.lexpos

此屬性是一個整數，包含輸入文本中的當前位置。如果修改該值，它將更改對token()的下一個調用的結果。在token規則函數中，它指向匹配文本之后的第一個字符。如果在規則中修改了該值，則將在新位置匹配下一個返回的token。

lexer.lineno

存儲在lexer中的行號屬性的當前值。PLY只指定屬性存在——它從不設置、更新或執行任何處理。如果您想跟蹤行號，您需要自己添加代碼(請參閱行號和位置信息一節)。

lexer.lexdata

存儲在lexer中的當前輸入文本。這是通過input()方法傳遞的字符串。除非你真的知道你在做什么，否則修改它可能不是一個好主意。

lexer.lexmatch

這是Python re.match()函數(PLY在內部使用)為當前令牌返回的原始匹配對象。如果您編寫了包含命名組的正則表達式，則可以使用它檢索這些值。注意:此屬性僅在由函數定義和處理token時更新。

4.19 Conditional lexing and start conditions

在高級解析應用程序中，具有不同的詞法分析狀態可能很有用。例如，您可能希望某個token或語法結構的出現觸發另一種類型的詞法分析。PLY支持一個特性，該特性允許將底層lexer放入一系列不同的狀態。每個狀態都可以有自己的token、詞法規則等等。該實現主要基于GNU flex的“啟動條件”特性。詳細信息可以在http://flex.sourceforge.net/manual/startconditions .html中找到。

要定義一個新的lexing狀態，必須首先聲明它。這是通過在lex文件中包含一個“states”聲明來實現的。例如:

states = (('foo','exclusive'),('bar','inclusive'),)

這個聲明聲明了兩個狀態，‘foo’和’bar’。狀態可分為兩類;“獨占exclusive”和“包含inclusive”。獨占狀態完全覆蓋lexer的默認行為。也就是說，lex只返回token并應用為該狀態定義的規則。包含狀態將附加狀態和規則添加到默認規則集。因此，除了為包含狀態定義的包含之外，lex還將返回默認定義的兩個包含。

一旦聲明了狀態，就通過在token/規則聲明中包含狀態名來聲明token和規則。例如:

t_foo_NUMBER = r'\d+' # Token 'NUMBER' in state 'foo' t_bar_ID = r'[a-zA-Z_][a-zA-Z0-9_]*' # Token 'ID' in state 'bar'def t_foo_newline(t):r'\n't.lexer.lineno += 1

通過在聲明中包含多個狀態名，可以在多個狀態中聲明token。例如:

t_foo_bar_NUMBER = r'\d+' # Defines token 'NUMBER' in both state 'foo' and 'bar'

另一種方法是，可以在所有狀態中使用名稱中的“ANY”聲明令牌:

t_ANY_NUMBER = r'\d+' # Defines a token 'NUMBER' in all states

如果沒有提供狀態名(通常是這種情況)，則令牌與一個特殊的狀態“INITIAL”關聯。例如，這兩個聲明是相同的:

t_foo_ignore = " \t\n" # Ignored characters for state 'foo'def t_bar_error(t): # Special error handler for state 'bar'pass

默認情況下，lexing在“初始”狀態下運行。此狀態包括所有通常定義的令牌。對于不使用不同狀態的用戶，這個事實是完全透明的。如果在進行詞法分析或解析時，希望更改詞法分析狀態，請使用begin()方法。例如:

def t_begin_foo(t):r'start_foo't.lexer.begin('foo') # Starts 'foo' state

要脫離狀態，可以使用begin()切換回初始狀態。例如:

def t_foo_end(t):r'end_foo't.lexer.begin('INITIAL') # Back to the initial state

狀態管理也可以通過堆棧來完成。例如:

def t_begin_foo(t):r'start_foo't.lexer.push_state('foo') # Starts 'foo' statedef t_foo_end(t):r'end_foo't.lexer.pop_state() # Back to the previous state

堆棧的使用在以下情況下非常有用:有許多方法可以進入新的lexing狀態，而您只是想在以后返回到以前的狀態。

舉個例子可能更清晰。假設您正在編寫一個解析器，并且希望獲取用大括號括起來的任意C代碼段。也就是說，每當遇到開始大括號“{”時，都希望讀取所包含的所有代碼，直到結束大括號“}”，并將其作為字符串返回。使用普通正則表達式規則來實現這一點幾乎是不可能的。這是因為大括號可以嵌套，可以包含在注釋和字符串中。因此，僅僅匹配第一個匹配的“}”字符是不夠的。下面是使用lexer狀態的方法:

# Declare the statestates = (('ccode','exclusive'),)# Match the first {. Enter ccode state.def t_ccode(t):r'\{'t.lexer.code_start = t.lexer.lexpos # Record the starting positiont.lexer.level = 1 # Initial brace levelt.lexer.begin('ccode') # Enter 'ccode' state# Rules for the ccode statedef t_ccode_lbrace(t): r'\{'t.lexer.level +=1 def t_ccode_rbrace(t):r'\}'t.lexer.level -=1# If closing brace, return the code fragmentif t.lexer.level == 0:t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos+1]t.type = "CCODE"t.lexer.lineno += t.value.count('\n')t.lexer.begin('INITIAL') return t# C or C++ comment (ignore) def t_ccode_comment(t):r'(/\*(.|\n)*?\*/)|(//.*)'pass# C stringdef t_ccode_string(t):r'\"([^\\\n]|(\\.))*?\"'# C character literaldef t_ccode_char(t):r'\'([^\\\n]|(\\.))*?\''# Any sequence of non-whitespace characters (not braces, strings)def t_ccode_nonspace(t):r'[^\s\{\}\'\"]+'# Ignored characters (whitespace)t_ccode_ignore = " \t\n"# For bad characters, we just skip over itdef t_ccode_error(t):t.lexer.skip(1)

在本例中，第一個“{”的出現導致lexer記錄起始位置并輸入一個新的狀態“ccode”。然后，一組規則匹配隨后輸入的各個部分(注釋、字符串等)。所有這些規則都只是丟棄令牌(通過不返回值)。但是，如果遇到右大括號，規則t_ccode_r大括號將收集所有代碼(使用前面記錄的起始位置)，存儲它，并返回一個包含所有文本的令牌“CCODE”。當返回令牌時，詞法分析狀態將恢復到初始狀態。

4.20 Miscellaneous Issues

• lexer要求以單個輸入字符串的形式提供輸入。由于大多數機器都有足夠的內存，因此很少會出現性能問題。但是，這意味著lexer目前不能用于流數據，例如打開的文件或套接字。這種限制主要是使用re模塊的副作用。您可以通過實現適當的def t_eof()文件末尾處理規則來解決這個問題。這里的主要復雜之處在于，您可能需要確保以某種方式將數據提供給lexer，這樣它就不會在令牌中間分裂。

• lexer應該能夠正確地處理作為令牌和模式匹配規則給出的Unicode字符串以及輸入文本。

• 您需要向re.compile()函數提供可選的標志，使用lex的reflags選項。例如:

  lex.lex(reflags=re.UNICODE | re.VERBOSE)

  默認情況下，reflags被設置為re.VERBOSE。如果您提供了自己的標志，您可能需要將其包含在PLY中以保持其正常行為。

• 由于lexer完全是用Python編寫的，所以它的性能在很大程度上取決于Python re模塊的性能。盡管lexer被編寫得盡可能的高效，但是當它被用于非常大的輸入文件時，它的速度并不快。如果關心性能，可以考慮升級到Python的最新版本，創建一個手寫的lexer，或者將lexer卸載到C擴展模塊中。

• 如果您打算創建一個手寫的lexer，并計劃與yacc一起使用它。，只需要符合以下要求:

  • 它必須提供一個token()方法，該方法返回下一個令牌，如果沒有更多的令牌可用，則返回None。
  • token()方法必須返回一個具有類型和值屬性的對象tok。如果使用行號跟蹤，那么標記還應該定義一個lineno屬性。

5. Parsing basics

yacc.py用于解析語言的語法，在展示示例之前，必須提到一些重要的背景知識。首先，語法通常用BNF語法指定。例如，如果您想解析簡單的算術表達式，您可以首先編寫一個明確的語法規范，如下所示:

expression : expression + term| expression - term| termterm : term * factor| term / factor| factorfactor : NUMBER| ( expression )

在語法中，數字、+、-、*和/等符號被稱為終結符，與原始輸入標記相對應。

諸如term和factor之類的標識符是指由一組終結符和其他規則組成的語法規則，這些被稱之為非終結符。

語言的語義行為通常使用一種稱為語法制導翻譯的技術來指定。在語法制導翻譯中，屬性與操作一起附加到給定語法規則中的每個符號。只要識別出特定的語法規則，動作就描述要做什么。例如，給定上面的表達式語法，您可以編寫一個像這樣的簡單計算器的規范:

理解語法制導翻譯的一個方式是將語法中的每個符號看做是一個對象，與每個符號相關聯的是一個表示其“狀態”的值，然后，語義動作被表示為操作符號和相關值的函數或方法的集合。

Yacc使用的解析技術，稱為LR解析或shift-reduce解析，LR解析是一種自下而上的技術。

LR解析通過棧來操作，下面有一個用于解析 3 + 5 * (10 - 20) 的棧操作，其中$表示輸入的結束。

如果棧中頂部元素可以合并成生成式左邊的表達式，則可以進行合并。解析的成功取決于最終棧中元素為空且沒有新輸入的token。

6. Yacc

ply.yacc 模塊實現了PLY中的內容解析。Yacc代表"Yet Another Compiler Compiler" ，采用了和Unix中一樣的名稱。

6.1 An example

如果你想要做一個簡單的語法表達式的解析，下面有一個簡單的例子：

# Yacc exampleimport ply.yacc as yacc# Get the token map from the lexer. This is required. from calclex import tokensdef p_expression_plus(p):'expression : expression PLUS term'p[0] = p[1] + p[3]def p_expression_minus(p):'expression : expression MINUS term'p[0] = p[1] - p[3]def p_expression_term(p):'expression : term'p[0] = p[1]def p_term_times(p):'term : term TIMES factor'p[0] = p[1] * p[3]def p_term_div(p):'term : term DIVIDE factor'p[0] = p[1] / p[3]def p_term_factor(p):'term : factor'p[0] = p[1]def p_factor_num(p):'factor : NUMBER'p[0] = p[1]def p_factor_expr(p):'factor : LPAREN expression RPAREN'p[0] = p[2]# Error rule for syntax errors def p_error(p):print("Syntax error in input!")# Build the parser parser = yacc.yacc()while True:try:s = raw_input('calc > ')except EOFError:breakif not s: continueresult = parser.parse(s)print(result)

在上述例子中，每一個語法規則規定義為一個python的函數，每個函數接收一個參數p，其中p為一個包含每個語法符號對應值的序列。p[i]的值是一個語法符號的映射，如：

def p_expression_plus(p):'expression : expression PLUS term'# ^ ^ ^ ^# p[0] p[1] p[2] p[3]p[0] = p[1] + p[3]

對應token來說，p[i]的值類似于在詞法分析中的屬性值 p.value 。對于非終端結點而言，當進行規約的時候，該值取決于p[0]中放置的內容決定。這個值可以是任何值。然而，最常見的值可能是簡單的Python類型、元組或實例。在本例中，我們依賴于NUMBER在其值字段中存儲整數值。所有其他規則只是執行各種類型的整數操作并傳播結果。

注意:負索引的使用在yacc中有特殊的意義——在本例中，特殊的p[-1]與p[3]沒有相同的值。有關詳細信息，請參閱“嵌入式操作”一節。

yacc規范中定義的第一個規則確定開始語法符號(在本例中，首先出現expression規則)。每當解析器規約了起始規則，并且沒有更多的輸入可用時，解析就會停止，并返回最終的值(這個值將是p[0]中放置的最上面的規則)。注意:可以使用yacc()的start關鍵字參數start指定另一個啟動符號。

定義p_error§規則是為了捕獲語法錯誤。有關詳細信息，請參閱下面的錯誤處理部分。

要構建解析器，請調用yacc.yacc()函數。這個函數查看模塊并嘗試為您指定的語法構造所有LR解析表。第一次調用yacc.yacc()時，您將得到這樣一條消息:

$ python calcparse.pyGenerating LALR tablescalc >

由于表的構造相對比較昂貴(特別是對于大型語法)，因此產生的解析表被寫到一個名為parsetab.py的文件中。此外，還有一個名為parser.out的調試文件創建。在隨后的執行中，yacc將從parsetab.py重新加載表，除非它檢測到底層語法的變化(在這種情況下，表和parsetab.py文件將重新生成)。這兩個文件都被寫到與指定解析器的模塊相同的目錄中。可以使用tabmodule關鍵字參數yacc()更改parsetab模塊的名稱。例如:

parser = yacc.yacc(tabmodule='fooparsetab')

如果在語法規范中檢測到任何錯誤，yacc.py將生成診斷消息，并可能引發異常。可以檢測到的錯誤包括:

• 重復的函數名(如果語法文件中有多個規則函數具有相同的名稱)。
• Shift/reduce和reduce/reduce由模糊語法生成的沖突
• 語法規則不規范
• 無限遞歸(永不終止的規則)
• 未使用的規則和令
• 未定義的規則和令牌

接下來的幾節將更詳細地討論語法規范。示例的最后一部分顯示了如何實際運行yacc()創建的解析器。要運行解析器，只需使用輸入文本字符串調用parse()。這將運行所有語法規則并返回整個解析的結果。這個結果返回值是在開始語法規則中分配給p[0]的值。

6.2 Combining Grammar Rule Functions

當語法規則相似時，可以將它們組合成一個函數。例如，考慮前面例子中的兩條規則:

def p_expression_plus(p):'expression : expression PLUS term'p[0] = p[1] + p[3]def p_expression_minus(t):'expression : expression MINUS term'p[0] = p[1] - p[3]

可以寫成一個函數，如下所示：

def p_expression(p):'''expression : expression PLUS term| expression MINUS term'''if p[2] == '+':p[0] = p[1] + p[3]elif p[2] == '-':p[0] = p[1] - p[3]

通常，任何給定函數的字符串都可以包含多個語法規則。所以，這樣寫也是合法的(盡管可能會讓人困惑):

def p_binary_operators(p):'''expression : expression PLUS term| expression MINUS termterm : term TIMES factor| term DIVIDE factor'''if p[2] == '+':p[0] = p[1] + p[3]elif p[2] == '-':p[0] = p[1] - p[3]elif p[2] == '*':p[0] = p[1] * p[3]elif p[2] == '/':p[0] = p[1] / p[3]

當將語法規則組合成單個函數時，通常所有規則都具有類似的結構(例如，相同數量的術語)。否則，相應的操作代碼可能比需要的更復雜。但是，可以使用len()處理簡單的情況。例如:

def p_expressions(p):'''expression : expression MINUS expression| MINUS expression'''if (len(p) == 4):p[0] = p[1] - p[3]elif (len(p) == 3):p[0] = -p[2]

解析性能是一個需要考慮的問題，您應該克制將太多條件處理放入單個語法規則的沖動，如這些示例所示。當您添加檢查以查看正在處理的語法規則時，實際上是在復制解析器已經執行的工作(即，解析器已經確切地知道它匹配的規則)。您可以通過為每個語法規則使用單獨的p_rule()函數來消除這種開銷。

6.3 Character Literals

如果需要，語法可以包含定義為單個字符文字的標記。例如:

def p_binary_operators(p):'''expression : expression '+' term| expression '-' termterm : term '*' factor| term '/' factor'''if p[2] == '+':p[0] = p[1] + p[3]elif p[2] == '-':p[0] = p[1] - p[3]elif p[2] == '*':p[0] = p[1] * p[3]elif p[2] == '/':p[0] = p[1] / p[3]

字符文字必須用引號括起來，如“+”。此外，如果使用了文本，則必須通過使用特殊的文本聲明在相應的lex文件中聲明它們。

# Literals. Should be placed in module given to lex()literals = ['+','-','*','/' ]

字符文字僅限于單個字符。因此，指定諸如’<=‘或’==‘之類的文字是不合法的。為此，使用常規的詞法規則(例如，定義一個規則，如t_EQ = r’==’)。

6.4 Empty Productions

yacc.py可以通過定義如下規則來處理空結果:

def p_empty(p):'empty :'pass

使用空結果可以直接使用“empty”作為符號，例如：

def p_optitem(p):'optitem : item'' | empty'...

注意:您可以在任何地方編寫空規則，只需指定右側為空即可。然而，我個人發現，寫一個“空”規則并用“空”來表示一個空的結果更容易閱讀，也更清楚地說明了您的意圖。

6.5 Changing the starting symbol

通常，在yacc規范中發現的第一個規則定義了開始語法規則(頂級規則)。要更改這一點，只需在文件中提供一個start說明符。例如:

start = 'foo'def p_bar(p):'bar : A B'# This is the starting rule due to the start specifier abovedef p_foo(p):'foo : bar X'...

在調試過程中使用start說明符可能很有用，因為您可以使用它來讓yacc構建更大語法的子集。為此，也可以指定起始符號作為yacc()的參數。例如:

parser = yacc.yacc(start='foo')

6.6 Dealing With Ambiguous Grammars

前面的例子中給出的表達式語法是用一種特殊的格式編寫的，以消除歧義。然而，在許多情況下，用這種格式編寫語法極其困難或尷尬。一種更自然的表達語法的方式是這樣一種更緊湊的形式:

expression : expression PLUS expression| expression MINUS expression| expression TIMES expression| expression DIVIDE expression| LPAREN expression RPAREN| NUMBER

不幸的是，這個語法規范是含糊不清的。例如，如果您正在解析字符串“3 * 4 + 5”，那么就無法知道操作符應該如何分組。例如，表達式的意思是“(3 * 4)+5”還是“3 *(4+5)”?

當 yacc.py中出現具有二義性的語法的時候，會出現“移入/規約”或”規約/規約“沖突，

當解析器生成器無法決定是減少規則還是更改解析堆棧上的符號時，將導致移入/規約沖突。例如，考慮字符串“3 * 4 + 5”和內部解析堆棧:

在本例中，當解析器達到步驟6時，它有兩個選項。一種是減少堆棧上的規則expr: expr * expr。另一個選項是在堆棧上移入”+“。根據上下文無關語法的規則，這兩個選項都是完全合法的。

默認情況下，所有的移入/規約沖突都是通過移入來解決的。因此，在上面的例子中，解析器總是將+移位而不是減少。雖然這種策略在很多情況下都有效(例如，“if-then”與“if-then-else”的情況)，但是對于算術表達式來說還不夠。事實上，在上面的例子中，移位+的決定是完全錯誤的——我們應該減少expr * expr，因為乘法比加法具有更高的數學優先級。

為了解決歧義，特別是在表達式語法中，yacc.py允許為單個標記分配優先級和關聯性。這是通過向語法文件添加一個變量優先級來實現的，如下所示:

precedence = (('left', 'PLUS', 'MINUS'),('left', 'TIMES', 'DIVIDE'),)

這個聲明指定加減具有相同的優先級，并且是左關聯的，而乘以/除以具有相同的優先級，并且是左關聯的。在優先聲明中，token從最低優先級排序到最高優先級。因此，這個聲明指定TIMES/DIVIDE的優先級高于PLUS/MINUS(因為它們出現在優先級規范的后面)。

優先規范通過將數值優先級值和關聯方向關聯到列出的標記來工作。例如，在上面的例子中，你得到:

PLUS : level = 1, assoc = 'left'MINUS : level = 1, assoc = 'left'TIMES : level = 2, assoc = 'left'DIVIDE : level = 2, assoc = 'left'

然后，這些值用于為每個語法規則附加一個數值優先值和關聯方向。這總是通過查看最右端符號的優先級來確定的。例如:

expression : expression PLUS expression # level = 1, left| expression MINUS expression # level = 1, left| expression TIMES expression # level = 2, left| expression DIVIDE expression # level = 2, left| LPAREN expression RPAREN # level = None (not specified)| NUMBER # level = None (not specified)

當遇到移位/規約沖突時，解析器生成器通過查看優先規則和關聯說明符來解決沖突。

• 如果當前令牌的優先級高于堆棧上的規則，則對其進行移位。
• 如果堆棧上的語法規則具有更高的優先級，則該規則進行規約
• 如果當前token和語法規則具有相同的優先級，則對左關聯規則規約，而對右關聯規則更改token
• 如果對優先級一無所知，則使用移位(默認值)解決移位/減少沖突。

例如，當"expression PLUS expression" 遇到下一個"TIMES"，則應該進行移入操作。相反，"expression TIMES expression"遇到““PLUS””則進行規約操作。

優先說明符技術的一個問題是，有時需要在某些上下文中更改操作符的優先級。例如，考慮“3 + 4 * -5”中的一元減運算符。

從數學上講，一元減號通常具有很高的優先級——在乘法之前求值。然而，在我們的優先說明符中，-的優先級比TIMES低。為了處理這個問題，可以為所謂的“虛擬令牌”提供優先規則，如下所示:

precedence = (('left', 'PLUS', 'MINUS'),('left', 'TIMES', 'DIVIDE'),('right', 'UMINUS'), # Unary minus operator)

現在，在語法文件中，我們可以這樣寫一元減號規則:

def p_expr_uminus(p):'expression : MINUS expression %prec UMINUS'p[0] = -p[2]

在這種情況下，%prec UMINUS覆蓋默認規則優先級——在優先說明符中將其設置為UMINUS。

當有多個語法規則可應用于給定的一組符號時，會導致Reduce/ Reduce沖突。這種沖突幾乎總是不好的，總是通過選擇語法文件中首先出現的規則來解決。當不同的語法規則以某種方式生成相同的符號集時，幾乎總是會引起Reduce/ Reduce沖突。例如:

在這種情況下，這兩條規則之間存在一個reduce/reduce沖突:

assignment : ID EQUALS NUMBERexpression : NUMBER

例如，如果你寫了“a=5”，解析的時候將不清楚到底是解析為assignment : ID EQUALS NUMBER 還是 assignment : ID EQUALS expression.

當出現規約/規約沖突的時候，yacc()將會打印下列警告信息：

WARNING: 1 reduce/reduce conflictWARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER)WARNING: rejected rule (expression -> NUMBER)

此消息標識沖突的兩條規則。但是，它可能不會告訴您解析器是如何達到這種狀態的。要嘗試解決這個問題，您可能需要查看語法和解析器 parser.out 的內容。

6.7 The parser.out file

跟蹤shift/reduce和reduce/reduce沖突是使用LR解析算法的一個更好的樂趣。為了幫助調試，yacc.py創建了一個名為“parser”的調試文件。當它生成解析表時。該文件的內容如下:

Unused terminals:GrammarRule 1 expression -> expression PLUS expressionRule 2 expression -> expression MINUS expressionRule 3 expression -> expression TIMES expressionRule 4 expression -> expression DIVIDE expressionRule 5 expression -> NUMBERRule 6 expression -> LPAREN expression RPARENTerminals, with rules where they appearTIMES : 3error : MINUS : 2RPAREN : 6LPAREN : 6DIVIDE : 4PLUS : 1NUMBER : 5Nonterminals, with rules where they appearexpression : 1 1 2 2 3 3 4 4 6 0Parsing method: LALRstate 0S' -> . expressionexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 1S' -> expression .expression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expressionPLUS shift and go to state 6MINUS shift and go to state 5TIMES shift and go to state 4DIVIDE shift and go to state 7state 2expression -> LPAREN . expression RPARENexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 3expression -> NUMBER .$ reduce using rule 5PLUS reduce using rule 5MINUS reduce using rule 5TIMES reduce using rule 5DIVIDE reduce using rule 5RPAREN reduce using rule 5state 4expression -> expression TIMES . expressionexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 5expression -> expression MINUS . expressionexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 6expression -> expression PLUS . expressionexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 7expression -> expression DIVIDE . expressionexpression -> . expression PLUS expressionexpression -> . expression MINUS expressionexpression -> . expression TIMES expressionexpression -> . expression DIVIDE expressionexpression -> . NUMBERexpression -> . LPAREN expression RPARENNUMBER shift and go to state 3LPAREN shift and go to state 2state 8expression -> LPAREN expression . RPARENexpression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expressionRPAREN shift and go to state 13PLUS shift and go to state 6MINUS shift and go to state 5TIMES shift and go to state 4DIVIDE shift and go to state 7state 9expression -> expression TIMES expression .expression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expression$ reduce using rule 3PLUS reduce using rule 3MINUS reduce using rule 3TIMES reduce using rule 3DIVIDE reduce using rule 3RPAREN reduce using rule 3! PLUS [ shift and go to state 6 ]! MINUS [ shift and go to state 5 ]! TIMES [ shift and go to state 4 ]! DIVIDE [ shift and go to state 7 ]state 10expression -> expression MINUS expression .expression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expression$ reduce using rule 2PLUS reduce using rule 2MINUS reduce using rule 2RPAREN reduce using rule 2TIMES shift and go to state 4DIVIDE shift and go to state 7! TIMES [ reduce using rule 2 ]! DIVIDE [ reduce using rule 2 ]! PLUS [ shift and go to state 6 ]! MINUS [ shift and go to state 5 ]state 11expression -> expression PLUS expression .expression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expression$ reduce using rule 1PLUS reduce using rule 1MINUS reduce using rule 1RPAREN reduce using rule 1TIMES shift and go to state 4DIVIDE shift and go to state 7! TIMES [ reduce using rule 1 ]! DIVIDE [ reduce using rule 1 ]! PLUS [ shift and go to state 6 ]! MINUS [ shift and go to state 5 ]state 12expression -> expression DIVIDE expression .expression -> expression . PLUS expressionexpression -> expression . MINUS expressionexpression -> expression . TIMES expressionexpression -> expression . DIVIDE expression$ reduce using rule 4PLUS reduce using rule 4MINUS reduce using rule 4TIMES reduce using rule 4DIVIDE reduce using rule 4RPAREN reduce using rule 4! PLUS [ shift and go to state 6 ]! MINUS [ shift and go to state 5 ]! TIMES [ shift and go to state 4 ]! DIVIDE [ shift and go to state 7 ]state 13expression -> LPAREN expression RPAREN .$ reduce using rule 6PLUS reduce using rule 6MINUS reduce using rule 6TIMES reduce using rule 6DIVIDE reduce using rule 6RPAREN reduce using rule 6

該文件中出現的不同狀態表示語法允許的每個可能的有效輸入標記序列。當接收輸入標記時，解析器將構建一個堆棧并尋找匹配的規則。每個狀態都跟蹤可能正在匹配的語法規則。在每個規則中，“.”字符表示該規則中解析的當前位置。此外，還列出了每個有效輸入token的操作。當發生移位/規約或規約/規約沖突時，未選擇的規則前面加上一個“！”。例如:

! TIMES [ reduce using rule 2 ]! DIVIDE [ reduce using rule 2 ]! PLUS [ shift and go to state 6 ]! MINUS [ shift and go to state 5 ]

通過查看這些規則(并進行一些實踐)，您通常可以找到大多數解析沖突的根源。還應該強調的是，并不是所有的shift-reduce沖突都是不好的。但是，確保正確解析它們的唯一方法是查看parser.out。

6.8 Syntax Error Handling

如果您正在創建一個供生產使用的解析器，那么語法錯誤的處理是非常重要的。一般來說，您不希望解析器在出現問題的第一個跡象時就舉手投降。相反，您希望它報告錯誤，如果可能的話進行恢復，并繼續解析，以便立即將輸入中的所有錯誤報告給用戶。這是在C、c++和Java等語言的編譯器中發現的標準行為。

通常，當語法錯誤在解析過程中發生時，會立即檢測到該錯誤(即，解析器只讀取錯誤源之外的任何標記)。但是，此時，解析器進入了一個恢復模式，可以使用該模式嘗試并繼續進一步解析。一般來說，LR解析器中的錯誤恢復是一個古老話題。yacc.py提供的恢復機制可以與Unix yacc相媲美，因此您可能想要查閱O’Reilly的《Lex and yacc》之類的書以獲得更詳細的信息。

當出現語法錯誤時，yacc.py執行以下步驟:

• 在第一次出現錯誤時，將調用用戶定義的p_error()函數，并將違規token作為參數。但是，如果語法錯誤是由于到達文件末尾，則調用p_error()，參數為None。然后，解析器進入“錯誤恢復”模式，在此模式中，在成功地將至少3個標記轉移到解析堆棧之前，它不會對p_error()進行后續調用
• 如果p_error()中沒有執行恢復操作，則使用一個特殊的錯誤token替換違規的前向令牌
• 如果錯誤的前向token已經設置為error，解析堆棧的頂部項將被刪除。
• 如果整個解析堆棧被解除，解析器將進入重啟狀態，并嘗試從初始狀態開始解析。
• 如果語法規則接受錯誤作為標記，它將被轉移到解析堆棧。
• 如果解析堆棧的頂部項是error，則在解析器成功轉換新符號或減少包含錯誤的規則之前，將丟棄前向標記。

6.9 Line Number and Position Tracking

編寫編譯器時，位置跟蹤常常是一個棘手的問題。默認情況下，PLY跟蹤所有token的行號和位置。這些資料可用以下功能提供:

• p.lineno(num). 返回行號
• p.lexpos(num). 返回相對于文本的相對位置

例如:

def p_expression(p):'expression : expression PLUS expression'line = p.lineno(2) # line number of the PLUS tokenindex = p.lexpos(2) # Position of the PLUS token

作為一個可選特性，yacc.py還可以自動跟蹤所有語法符號的行號和位置。但是，這種額外的跟蹤需要額外的處理，并且會顯著降低解析速度。因此，必須通過將tracking=True選項傳遞給yacc.parse()來啟用它。例如:

yacc.parse(data,tracking=True)

一旦啟用，lineno()和lexpos()方法就可以用于所有語法符號。此外，還可以使用另外兩種方法:

• p.linespan(num). 返回一個元組(起始行、結束行)
• p.lexspan(num). 返回一個元組(start,end)，表示起始結束位置。

def p_expression(p):'expression : expression PLUS expression'p.lineno(1) # Line number of the left expressionp.lineno(2) # line number of the PLUS operatorp.lineno(3) # line number of the right expression...start,end = p.linespan(3) # Start,end lines of the right expressionstarti,endi = p.lexspan(3) # Start,end positions of right expression

注意:lexspan()函數只返回到最后一個語法符號開始的值范圍

雖然PLY可以方便地跟蹤所有語法符號的位置信息，但這通常是不必要的。例如，如果您只是在錯誤消息中使用行號信息，那么您通常可以在語法規則中鍵入特定的token。例如:

def p_bad_func(p):'funccall : fname LPAREN error RPAREN'# Line number reported from LPAREN tokenprint("Bad function call at line", p.lineno(2))

類似地，如果使用p.set_lineno()方法只在需要的地方有選擇地傳播行號信息，那么解析性能可能會更好。例如:

def p_fname(p):'fname : ID'p[0] = p[1]p.set_lineno(0,p.lineno(1))

PLY不保留已解析規則中的行號信息。如果您正在構建一個抽象語法樹，并且需要行號，那么您應該確保行號出現在樹本身中。

6.10 AST Construction

yacc.py 并沒有提供特殊的方法來構造AST，然而這種構造可以自己來輕松實現。

構造樹的最簡單方法是在每個語法規則函數中創建和傳播一個元組或列表。有很多方法可以做到這一點，其中一個例子是這樣的:

def p_expression_binop(p):'''expression : expression PLUS expression| expression MINUS expression| expression TIMES expression| expression DIVIDE expression'''p[0] = ('binary-expression',p[2],p[1],p[3])def p_expression_group(p):'expression : LPAREN expression RPAREN'p[0] = ('group-expression',p[2])def p_expression_number(p):'expression : NUMBER'p[0] = ('number-expression',p[1])

另一種方法是為不同類型的抽象語法樹節點創建一組數據結構，并在每個規則中將節點分配給p[0]。例如:

class Expr: passclass BinOp(Expr):def __init__(self,left,op,right):self.type = "binop"self.left = leftself.right = rightself.op = opclass Number(Expr):def __init__(self,value):self.type = "number"self.value = valuedef p_expression_binop(p):'''expression : expression PLUS expression| expression MINUS expression| expression TIMES expression| expression DIVIDE expression'''p[0] = BinOp(p[1],p[2],p[3])def p_expression_group(p):'expression : LPAREN expression RPAREN'p[0] = p[2]def p_expression_number(p):'expression : NUMBER'p[0] = Number(p[1])

這種方法的優點是，它可以更容易地將更復雜的語義、類型檢查、代碼生成和其他特性附加到節點類。

為了簡化樹遍歷，可以為解析樹節點選擇一個非常通用的樹結構。例如:

class Node:def __init__(self,type,children=None,leaf=None):self.type = typeif children:self.children = childrenelse:self.children = [ ]self.leaf = leafdef p_expression_binop(p):'''expression : expression PLUS expression| expression MINUS expression| expression TIMES expression| expression DIVIDE expression'''p[0] = Node("binop", [p[1],p[3]], p[2])

6.11 Embedded Actions

yacc使用的解析技術只允許在規則末尾執行操作。例如，假設您有這樣一個規則:

def p_foo(p):"foo : A B C D"print("Parsed a foo", p[1],p[2],p[3],p[4])

在本例中，所提供的操作代碼僅在解析完所有符號A、B、C和D之后執行。然而，有時在解析的中間階段執行小的代碼片段是有用的。例如，假設您想在解析A之后立即執行某個操作。要做到這一點，可以這樣寫一個空規則:

def p_foo(p):"foo : A seen_A B C D"print("Parsed a foo", p[1],p[3],p[4],p[5])print("seen_A returned", p[2])def p_seen_A(p):"seen_A :"print("Saw an A = ", p[-1]) # Access grammar symbol to leftp[0] = some_value # Assign value to seen_A

在本例中，空seen_A規則在將A轉移到解析堆棧后立即執行。在這個規則中，p[-1]指堆棧上立即出現在seen_A符號左側的符號。在這種情況下，它將是上面foo規則中A的值。與其他規則一樣，可以通過簡單地將嵌入式操作分配給p[0]來返回值。

嵌入式操作的使用有時會引入額外的移位/規約沖突。例如，這個語法沒有沖突:

def p_foo(p):"""foo : abcd| abcx"""def p_abcd(p):"abcd : A B C D"def p_abcx(p):"abcx : A B C X"

然而，如果你像這樣在規則中插入一個嵌入的動作，

def p_foo(p):"""foo : abcd| abcx"""def p_abcd(p):"abcd : A B C D"def p_abcx(p):"abcx : A B seen_AB C X"def p_seen_AB(p):"seen_AB :"

將引入一個額外的shift-reduce沖突。這個沖突是由于相同的符號C出現在abcd和abcx規則中。解析器可以移動符號(abcd規則)或規約空規則seen_AB (abcx規則)。

嵌入式規則的一個常見用途是控制解析的其他方面，比如局部變量的范圍。例如，如果您正在解析C代碼，您可能會這樣編寫代碼:

def p_statements_block(p):"statements: LBRACE new_scope statements RBRACE"""# Action code...pop_scope() # Return to previous scopedef p_new_scope(p):"new_scope :"# Create a new scope for local variabless = new_scope()push_scope(s)...

在這種情況下，在解析LBRACE({)符號之后，嵌入的動作new_scope立即執行。這可能會調整內部符號表和解析器的其他方面。在規則statements_block完成后，代碼可以撤消在嵌入式操作(例如，pop_scope())中執行的操作。

6.12 Miscellaneous Yacc Notes

• 默認情況下，yacc.py依賴于lex.py進行標記。但是，可以提供另一種token，如下:

  parser = yacc.parse(lexer=x)

  在本例中，x必須是Lexer對象，該對象至少具有用于檢索下一個token的x.token()方法。如果向yacc.parse()提供輸入字符串，lexer還必須有一個x.input()方法。

• 默認情況下，yacc以調試模式生成表(調試模式生成解析器)。輸出文件和其他輸出)。若要禁用此功能，請使用

  parser = yacc.yacc(debug=False)

• 要更改parsetab.py文件的名稱，請使用:

  parser = yacc.yacc(tabmodule="foo")

  通常，parsetab.py文件與定義解析器的模塊放在同一個目錄中。如果您想將它放到其他地方，您可以為tabmodule提供一個絕對的包名。在這種情況下，表將寫在那里。

• 要更改寫入parsetab.py文件(和其他輸出文件)的目錄，請使用:

  parser = yacc.yacc(tabmodule="foo",outputdir="somedirectory")

  注意:除非指定的目錄也位于Python的路徑上(sys.path)，否則后續的表文件導入將失敗。一般來說，最好使用tabmodule參數指定目標，而不是直接使用outputdir參數指定目錄。

• 要防止yacc生成任何類型的解析器表文件，請使用:

  parser = yacc.yacc(write_tables=False)

  注意:如果禁用表生成，yacc()將在每次運行時重新生成解析表(這可能需要一段時間，這取決于語法的大小)。

• 若要在解析期間打印大量調試，請使用:

  parser.parse(input_text, debug=True)

• 由于生成LALR表的成本相對較高，因此以前生成的表將被緩存并盡可能重用。重新生成表的決定是通過對所有語法規則和優先規則進行MD5校驗和來確定的。只有在不匹配的情況下才會重新生成表。

  應該注意的是，表生成相當高效，即使對于涉及大約100條規則和幾百種狀態的語法也是如此。

• 由于LR解析是由表驅動的，所以解析器的性能在很大程度上獨立于語法的大小。最大的瓶頸將是lexer和語法規則中代碼的復雜性。

• yacc()還允許將解析器定義為類和閉包(請參閱關于lexer的替代規范的部分)。但是，請注意在單個模塊(源文件)中只能定義一個解析器。如果您試圖在同一個源文件中定義多個解析器，可能會出現各種錯誤檢查和驗證步驟，從而產生混淆的錯誤消息。

• 生產規則的裝飾器必須更新包裝函數的行號。wrapper.co_firstlineno = func.__code__.co_firstlineno:

  from functools import wrapsfrom nodes import Collectiondef strict(*types):def decorate(func):@wraps(func)def wrapper(p):func(p)if not isinstance(p[0], types):raise TypeErrorwrapper.co_firstlineno = func.__code__.co_firstlinenoreturn wrapperreturn decorate@strict(Collection)def p_collection(p):"""collection : sequence| map"""p[0] = p[1]

7. Multiple Parsers and Lexers

在高級解析應用程序中，您可能希望擁有多個解析器和lexer。

一般來說，這不是問題。然而，要使它工作，您需要仔細確保所有內容都正確地連接起來。首先，確保保存lex()和yacc()返回的對象。例如:

lexer = lex.lex() # Return lexer objectparser = yacc.yacc() # Return parser object

接下來，在解析時，確保將parse()函數引用到它應該使用的lexer。例如:

parser.parse(text,lexer=lexer)

如果忘記這樣做，解析器將使用最后創建的lexer——這并不總是您想要的。

在lexer和parser規則函數中，這些對象也是可用的。在lexer中，令牌的“lexer”屬性引用觸發規則的lexer對象。例如:

def t_NUMBER(t):r'\d+'...print(t.lexer) # Show lexer object

在解析器中，“lexer”和“parser”屬性分別引用lexer和parser對象。

def p_expr_plus(p):'expr : expr PLUS expr'...print(p.parser) # Show parser objectprint(p.lexer) # Show lexer object

如果需要，可以將任意屬性附加到lexer或解析器對象。例如，如果希望有不同的解析模式，可以將模式屬性附加到解析器對象上，稍后再進行研究。

8. Using Python’s Optimized Mode

因為PLY使用來自doc-string的信息，所以在正常模式下運行Python解釋器(即，而不是-O或-OO選項)。但是，如果您像這樣指定優化模式:

lex.lex(optimize=1)yacc.yacc(optimize=1)

然后，當Python以優化模式運行時，可以使用PLY。要使此工作正常，請確保首先在正常模式下運行Python。第一次生成詞法分析和解析表之后，以優化模式運行Python。PLY將使用不需要doc字符串的表。

注意:在優化模式下運行PLY會禁用大量錯誤檢查。您應該只在項目已穩定且不需要進行任何調試時才這樣做。優化模式的目的之一是顯著減少編譯器的啟動時間(假設所有內容都已正確指定并正常工作)。

9. Advanced Debugging

調試編譯器通常不是一項容易的任務。PLY通過使用Python的日志模塊提供了一些高級的對角線功能。下面兩部分將對此進行描述:

9.1 Debugging the lex() and yacc() commands

lex()和yacc()命令都具有可以使用debug標志啟用的調試模式。例如:

lex.lex(debug=True)yacc.yacc(debug=True)

通常，調試生成的輸出要么路由到標準錯誤，要么(在yacc()的情況下)路由到文件parser.out。通過提供一個日志對象，可以更仔細地控制這個輸出。下面是一個例子，它添加了關于不同調試消息來自何處的信息:

# Set up a logging objectimport logginglogging.basicConfig(level = logging.DEBUG,filename = "parselog.txt",filemode = "w",format = "%(filename)10s:%(lineno)4d:%(message)s")log = logging.getLogger()lex.lex(debug=True,debuglog=log)yacc.yacc(debug=True,debuglog=log)

如果提供自定義日志記錄器，則可以通過設置日志記錄級別來控制生成的調試信息的數量。通常，調試消息在調試、信息或警告級別發出。

PLY的錯誤消息和警告也使用日志記錄接口生成。這可以通過使用errorlog參數傳遞日志對象來控制。

lex.lex(errorlog=log)yacc.yacc(errorlog=log)

如果希望完全消除警告，可以傳入具有適當過濾器級別的日志對象，或者使用lex或yacc中定義的NullLogger對象。例如:

yacc.yacc(errorlog=yacc.NullLogger())

9.2 Run-time Debugging

若要啟用解析器的運行時調試，請使用debug選項進行解析。這個選項可以是整數(它只是打開或關閉調試)，也可以是logger對象的實例。例如:

log = logging.getLogger()parser.parse(input,debug=log)

如果傳遞了日志對象，則可以使用其篩選級別來控制生成了多少輸出。INFO級別用于生成關于規則縮減的信息。調試級別將顯示有關解析堆棧、令牌轉換和其他細節的信息。錯誤級別顯示與解析錯誤相關的信息。

對于非常復雜的問題，您應該傳遞一個日志對象，該對象將重定向到一個文件，在執行后，您可以更容易地檢查輸出。

10. Packaging Advice

如果您正在分發一個使用PLY的包，您應該花一些時間考慮如何處理自動生成的文件。例如，yacc()函數生成的parsetab.py文件。

在PLY-3.6中，表文件創建在與定義解析器的文件相同的目錄中。這意味著parsetab.py文件將與解析器規范共存。就打包而言，這可能是最簡單、最理智的管理方法。您不需要給yacc()任何額外的參數，它應該只是“工作”。

一個關注點是parsetab.py文件本身的管理。例如，您應該將該文件簽入版本控制(例如GitHub)，它應該作為普通文件包含在包分發版中，還是應該讓PLY在用戶安裝您的包時自動生成它?

從PLY -3.6開始，parsetab.py文件應該兼容所有Python版本，包括Python 2和Python 3。因此，如果在python3上使用，用python2生成的表文件應該可以正常工作。因此，如果需要的話，自己分發parsetab.py文件應該是相對無害的。但是，請注意，如果將來對文件的格式進行了增強或更改，那么PLY的舊/新版本可能會嘗試重新生成文件。

為了使表文件的生成更易于安裝，您可以使用-m選項或類似的方法使解析器文件可執行。例如:

# calc.py......def make_parser():parser = yacc.yacc()return parserif __name__ == '__main__':make_parser()

然后可以使用python -m calc .py之類的命令生成表。另外，setup.py腳本可以導入模塊并使用make_parser()創建解析表。

如果愿意犧牲一點啟動時間，還可以指示PLY不要使用yacc編寫表。yacc.yacc(write_tables=False, debug=False)。在此模式下，PLY將每次重新生成解析表。對于一個小語法，您可能不會注意到。對于大型語法，您可能應該重新考慮—解析表的目的是顯著加快這個過程。

在操作過程中，正常情況是PLY生成診斷錯誤消息(通常打印為標準錯誤)。這些都是完全使用日志模塊生成的。如果希望重定向這些消息或使其保持靜默，可以將自己的日志對象提供給yacc()。例如:

import logginglog = logging.getLogger('ply')...parser = yacc.yacc(errorlog=log)

11. Where to go from here?

PLY分布的examples目錄包含幾個簡單的示例。有關理論和底層實現細節或LR解析，請參閱編譯器教科書。

總結

以上是生活随笔為你收集整理的PLY文档翻译——利用Python进行词法和语法分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。