Python ply包的正确食用手册

小胖鱼说事实 發表於 2021-11-9 03:38:00

包的下载地址：dabeaz/ply: Python Lex-Yacc (package download)
官方文档地址：dabeaz/ply: Python Lex-Yacc (official document)
貌似本体是其他学校的编译课设...那确实不知道比我们高到哪里去了。
这个包提供了比较强大的 Lex / Yacc 工具，能够完成不太复杂庞大的语法的词法、语法分析，对于学校的大作业和课设来说是足够的。
官方文档中介绍了该包的基本使用方法，举的例子是表达式解析。我在使用该包做MIPS汇编的语法检查时（代码可见：Github: LiuRunky - SEUCSE-Lab-Minisys-1A/assembler-src），用到了大部分的特性，并且有一些文档中没有写出或强调的心得，于是就在这里一边整理一边记录。
目录：
Lex
　　1. 简单介绍
　　2. 基本结构
　　3. Token 类型列表
　　4. Token 匹配规则的声明
　　5. 特殊的匹配规则
　　6. 匹配优先级（Token 间）
　　7. 匹配优先级（Token 内）
　　8. 函数方式定义支持的操作
　　9. 匹配规则的返回值
　　10. 一些可能有用的东西
Yacc
　　1. 简单介绍
　　2. 基本结构
　　3. Production 匹配规则的声明
　　4. 特殊的匹配规则
　　5. Production 类型的组成与使用
　　6. 匹配完成后的进阶操作
　　7. 产生式中简单符号的简化写法
　　8. 一些可能有用的东西
 
<hr>
 
Lex
 
1. 简单介绍
ply 包提供的 Lex 工具能够对于给定的文本进行词法分析，内部的实现方式是通过正则匹配获得一个文本中包含 Token 的列表，而我们要做的工作就是给定用于匹配的正则表达式。
其中 Token 是一个形式如下的四元组：。其中 type 表示词的类型（比如 variable / number / string，由我们来命名），value 就是文本中匹配上的内容（比如 "114514" / "0x1234" 都是合法的 number 类型），lineno 表示词出现的行号，lexpos 表示词出现在文本中的第几个字符。一般来说 type 和 value 比较关键，而 lineno 和 lexpos 一般用于生成分析的报错信息。
 
2. 基本结构
按照功能来分类的话，整个 ply Lex 的代码（不含主函数内）分为如下三个部分（细节在之后会展开说）：
<div class="cnblogs_code">
<pre># 1. 包的引入
from ply import lex

# 2. Token类型列表的声明
tokens = (
'TOKEN_1', 'TOKEN_2', 'TOKEN_3'
)

# 3. Token匹配规则的声明（字符串，函数）
t_TOKEN_1 = r"""reg_expr_1"""
t_TOKEN_2 = r"""reg_expr_2"""

def t_TOKEN_3(t):
r"""reg_expr_3"""
return t</pre>
</div>
至于主函数内的调用，可以如下进行（在真正 Lex Yacc 联合使用的时候不需要调用 lexer.input(data)，这是因为在 Yacc 内会自动地隐式调用 Lex，不过这个之后再说）：
<div class="cnblogs_code">
<pre>if __name__ == '__main__':
data = 'reg_expr_3reg_expr_2reg_expr_1'

lexer = lex.lex()
lexer.input(data)

while True:
 token = lexer.token()
 print(token)
 if not token:
 break</pre>
</div>
虽然上面的例子毫无卵用，但是其实是可以运行的。运行以上代码，结果如下：
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211108101326562-722867577.png" alt="" width="229" height="114" loading="lazy">
其中，输出了一行 None 是因为使用 lexer.token() 会自动获取下一 Token，直到读到文本末尾则返回 None。而 WARNING 中涉及的规则之后再议（其实不鸟它也完全没关系）。
 
3. Token 类型列表
从上面的例子可以看出来，Token 类型列表 tokens 就是一个简单的、由字符串组成的元组，其中每一个字符串表示一种 Token 的名称。不过这里只是声明了“有一种叫这个的 Token”，具体的匹配规则和匹配成功后的操作需要在之后补充完整。
需要注意的是，Token 名称最好定义成全大写字母。这是因为要与 Yacc 中的产生式进行区分（产生式一般定义成全小写字母），这样在写 Yacc 部分的代码时不容易混淆。
一些特殊的规则，比如 error（匹配不上时的操作）、ignore（需要忽略的字符）、literals（长度为1的符号的简化定义方法），不需要在 Token 类型列表中出现，只需要在 Token 匹配规则中声明 t_error、t_ignore，literals 则需要声明一个符号的 List。可以看出来，这些特殊规则的名称是全小写字母。
 
4. Token 匹配规则的声明
上文已经介绍过了，Token 匹配规则的声明有两种方式：字符串与函数。无论哪种方式，都需要与 Token 名称相对应、在名称前加上"t_"（比如 Token 叫  "TOKEN_TYPE_1"，那么匹配规则就应该命名为 "t_TOKEN_TYPE_1"）。
可以认为字符串方式定义的规则是简化版的函数方式，即以下两种定义方式在功能上是等价的：
<div class="cnblogs_code">
<pre>t_TOKEN = r"""expr"""

def t_TOKEN(t)
r"""expr"""
return t</pre>
</div>
简单比较两者的区别的话，字符串方式比较简单（只是进行匹配）、代码长度短，而函数方式能够在匹配成功后进行自定义的操作、功能更强。两者除了功能以外，还在匹配优先级上有所区别，相对而言函数方式的优先级比较容易规定，这个在之后专门开了两小节展开说。如果不放心的话可以全定义成函数方式。
之前代码给出的匹配规则有点太弱了，现在给两个画风稍微正常一点的：
<div class="cnblogs_code">
<pre>def t_IDNAME(t):
r"""*"""
return t

def t_VALUE(t):
r"""(0+)|(+)|(+)"""
return t</pre>
</div>
其中，t_IDNAME 约定了变量名的匹配规则（首字母不为数字，之后可以是字母或数字；原代码不是C语言的规则，所以没考虑下划线），而 t_VALUE 约定了数值的匹配规则（可以是二进制、十进制、十六进制，当为二进制时末尾必须有 "b" 或 "B"，当为十六进制时开头必须为 "0x" 或 "0X"）。
这些匹配规则都是需要通过正则表达式给出的，如果不太了解Python的规则的话可以参考Python 正则表达式 | 菜鸟教程 。
 
5. 特殊的匹配规则
(1) t_ignore：在匹配时忽略的一些字符，比如空格与制表符 "\t"
一个比较常用的定义方式如下，过滤了空格与 "\t"，注意这里不为raw string（由于 t_ignore 属于优先级最低的规则了，所以往往用字符串方式定义，类似的用法可见官方文档4.8 - literal characters）：
<div class="cnblogs_code">
<pre>t_ignore = ' \t'</pre>
</div>
不过这样存在了一个问题：如果我们在 t_ignore 中规定过滤空格，那么就不能用词法分析直接获得含空格的 Token（比如C中的 "long long"类型）。示例代码与运行结果如下：
<div class="cnblogs_code"><img src="https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif" id="code_img_closed_bbfcd430-5794-4bb3-889f-c80560340005" class="code_img_closed"><img src="https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif" id="code_img_opened_bbfcd430-5794-4bb3-889f-c80560340005" class="code_img_opened" style="display: none">
<div id="cnblogs_code_open_bbfcd430-5794-4bb3-889f-c80560340005" class="cnblogs_code_hide">
<pre># 1. 包的引入
from ply import lex

# 2. Token类型列表的声明
tokens = (
'TOKEN_1', 'TOKEN_2', 'TOKEN_3'
)

# 3. Token匹配规则的声明（字符串，函数）
t_TOKEN_1 = r"""long long""" # 优先级最高
t_TOKEN_2 = r"""longlong""" # 优先级次高
t_TOKEN_3 = r"""long""" # 优先级最低
t_ignore = ' \t'

if __name__ == '__main__':
data = 'long long longlong'

lexer = lex.lex()
lexer.input(data)

while True:
 token = lexer.token()
 print(token)
 if not token:
 break</pre>
</div>
示例代码</div>
<div class="cnblogs_code"><img src="https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif" id="code_img_closed_5f8d88b7-caf5-4fb9-88ff-40625cb10e55" class="code_img_closed"><img src="https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif" id="code_img_opened_5f8d88b7-caf5-4fb9-88ff-40625cb10e55" class="code_img_opened" style="display: none">
<div id="cnblogs_code_open_5f8d88b7-caf5-4fb9-88ff-40625cb10e55" class="cnblogs_code_hide">
<pre>> WARNING: No t_error rule is defined
> LexToken(TOKEN_3,'long',1,0)
> LexToken(TOKEN_3,'long',1,5)
> LexToken(TOKEN_1,'longlong',1,10)
> None</pre>
</div>
运行结果</div>
(2) t_error：在匹配失败时的动作
一般用于报错，没什么特别高级的功能。写了和不写差距不大，大概只是消除 WARNING 吧。
<div class="cnblogs_code">
<pre>def t_error(t):
raise Exception('Lex error {} at line {}, illegal character {}'
 .format(t.value, t.lineno, t.value))</pre>
</div>
(3) literals：一些长度为1的简单符号可以这样定义
具体信息参见 Yacc 部分的章节 Yacc： 7. 产生式中简单符号的简化写法
(4) 其他：t_eof 写和不写感觉是真没区别...另外的规则参考官方文档吧，不过貌似就只有这三个。
 
6. 匹配优先级（Token 间）
优先级规则其实是 ply 包中最重要的内容了（毕竟别的东西都封装好了），而官方文档在这里讲的太粗了。我在文档的基础上再多补充些内容。
之前说到用字符串方式和函数方式定义匹配规则在优先级方面有所区别，具体区别如下：
(1) 如果用字符串方式定义，那么用于匹配的正则表达式越长则匹配优先级越高；
(2) 如果用函数方式定义，函数在代码中出现的位置越靠前则匹配优先级越高；
(3) 用函数方式定义的匹配规则优先级永远高于用字符串定义的。
这也是为什么说“不确定就用函数”，因为函数相对字符串更容易控制优先级。一般来说，用字符串方式定义的规则只有 t_ignore 和一些不容易成为其他规则前缀的匹配规则，比如逗号 ","、分号 ";" 一般是可以用字符串方式定义的；而保留字（如 "int"、"double"）则不合适，因为其容易被识别成变量名。
官方文档关于优先级的讨论到前文的规则 (1) (2) (3) 就结束了，但在实际使用中真正容易遇到的问题却被忽略了：变量名与保留字冲突应该如何解决？
根据对于字符串定义方式的分析，我们知道了保留字应当用函数方式定义（保留字 > 变量名）；但是在现实中，我们经常可能定义一个前缀是保留字的变量，比如：
<div class="cnblogs_code">
<pre>int int_number = 1;
bool true_or_false = true;</pre>
</div>
如果我们规定保留字的优先级高于变量名，那么经过词法分析，我们会得到这样的 Token："int", "int", "_number", "=", "1", ";", "bool", "true", "_or_false", "=", "true", ";"。显然，"int_number" 和 "true_or_false" 这两个变量的解析是存在问题的，而这样的问题在真正debug遇到的时候很难定位到。
如果想要解决这样的问题，我们又需要规定前缀为保留字的变量优先级高于保留字（变量名 > 保留字），这下就产生矛盾了。
对于这样的问题没有一个简单的解决方法，我们必须通过分解问题来解决。我想出的解决方案是，将变量名分为两类：保留字前缀类（必须为保留字+其他字符）和非保留字前缀类。保留字前缀类的优先级高于保留字，非保留字前缀类的优先级低于保留字。不过这样一来保留字类的匹配规则就会长得十分恶心，必须考虑到所有的保留字才能实现，所以我写了一个C++代码来根据保留字列表自动生成保留字前缀类的匹配规则。主要思想是对保留字建 trie 树、打标记，然后在 trie 树上 dfs，如果遇到标记（保留字的结尾）就再进行第二个 dfs，从而生成描述保留字与保留字之间互为前缀关系的匹配规则。
<div class="cnblogs_code"><img src="https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif" id="code_img_closed_77e91956-f058-47ab-bbd7-8031e9ecdfbe" class="code_img_closed"><img src="https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif" id="code_img_opened_77e91956-f058-47ab-bbd7-8031e9ecdfbe" class="code_img_opened" style="display: none">
<div id="cnblogs_code_open_77e91956-f058-47ab-bbd7-8031e9ecdfbe" class="cnblogs_code_hide">
<pre>#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_SYMBOL=300;
const int MAX_STR_LEN=100;
const int MAX_NODE_NUM=10000;

int symbol=63;
string full_collec="";

int mapping[300];
char rmapping;
bool init_symbol;
bool extra_bslash;

int tot=1;
int tag;
int trie;

bool pool;
char pref;

vector<string> solve(int x,int pos,int st_pos)
{
vector<string> ans;
if(tag && pos!=st_pos)
 return ans;

memset(pool,false,sizeof(pool));

vector<int> v;
for(int i=0;i<symbol;i++)
 if(trie)
 pool=true,v.emplace_back(i);

vector<pii> v_res;
for(int i=0;i<symbol;)
{
 while(i<symbol && pool)
 i++;
 if(i==symbol)
 break;

 int j=i+1;
 while(j<symbol && !pool && !init_symbol)
 j++;
 v_res.emplace_back(pii(i,j-1));
 i=j;
}

if(v.empty())
 return ans;

string expr;
for(int i=st_pos;i<pos;i++)
 expr=expr+pref;
expr=expr+'[';
for(pii tmp: v_res)
{
 char l=rmapping,r=rmapping;
 if(l==r)
 {
 if(extra_bslash)
 expr=expr+'\\';
 expr=expr+l;
 }
 else
 expr=expr+l+'-'+r;
}
expr=expr+']';
ans.emplace_back(expr);

for(int y: v)
{
 pref=rmapping;
 vector<string> ans_nxt=solve(trie,pos+1,st_pos);
 ans.insert(ans.end(),ans_nxt.begin(),ans_nxt.end());
}
return ans;
}

map<string,vector<string>> combine;

void dfs(int x,int pos)
{
vector<int> v;
for(int i=0;i<symbol;i++)
 if(trie)
 v.emplace_back(i);

if(tag)
{
 string str_pref,expr;
 for(int i=0;i<pos;i++)
 str_pref=str_pref+pref;

 vector<string> v_mid=solve(x,pos,pos);
 if(v_mid.size()>1)
 {
 expr=expr+'(';
 for(int i=0;i<v_mid.size();i++)
 expr=expr+v_mid+(i+1==v_mid.size()?')':'|');
 }
 else
 if(!v_mid.empty())
 expr=expr+v_mid[0];
 expr=expr+full_collec+(v_mid.empty()?'+':'*');
 combine.emplace_back(str_pref);
}

for(int y: v)
{
 pref=rmapping;
 dfs(trie,pos+1);
}
}

int n;
char buf;

void init()
{
init_symbol[0]=true;
for(int i=0;i<26;i++)
 mapping['a'+i]=i,rmapping='a'+i;

init_symbol[26]=true;
for(int i=0;i<26;i++)
 mapping['A'+i]=26+i,rmapping[26+i]='A'+i;

init_symbol[52]=true;
for(int i=0;i<10;i++)
 mapping['0'+i]=52+i,rmapping[52+i]='0'+i;

init_symbol[62]=extra_bslash[62]=false;
mapping['_']=62,rmapping[62]='_';
}

int main()
{
freopen("keywords.txt","r",stdin);

init();

while(~scanf("%s",buf))
{
 n=strlen(buf);

 int cur=1;
 for(int i=0;i<n;i++)
 {
 int ch=mapping];
 if(!trie)
 trie=++tot;
 cur=trie;
 }
 tag=1;
}

/*
for(int i=1;i<=tot;i++)
 for(int j=0;j<26;j++)
 if(trie)
 printf("trie[%d][%c]=%d\n",i,char(j+'a'),trie);
*/

pref[0]='\0';
dfs(1,0);

vector<string> items;
map<string,vector<string>>::iterator it;
for(it=combine.begin();it!=combine.end();it++)
{
 string r=it->first;
 vector<string> vl=it->second;

 sort(vl.begin(),vl.end());
 reverse(vl.begin(),vl.end());

 string item;
 if(vl.size()>1)
 item=item+'(';
 for(int i=0;i+1<vl.size();i++)
 {
 item=item+vl+'|';
 if((i+1)%5==0)
 item=item+'\n';
 }
 item=item+vl.back();
 if(vl.size()>1)
 item=item+')';

 item=item+r;
 items.emplace_back(item);
}

for(int i=0;i<items.size();i++)
{
 cout<<"(\n"<<items<<"\n)";
 if(i+1<items.size())
 cout<<'|';
 cout<<'\n';
}
return 0;
}</pre>
</div>
View Code</div>
如果使用的话，需要根据实际需求修改的包括全局变量的 symbol（保留字数量）、full_collec（保留字中所有可能出现的字符，用正则表达式给出），以及 init() 函数中字符对可用字符标号的映射规则 mapping 与其逆映射 rmapping。另外，init_symbol = true 表示标号 i 为某一类连续可用字符的开始（这里的“开始”指的是 "0-9" 中的 "0" 和 "a-z" 中的 "a" 等）或单独的字符（比如 "_" 和 "$" 等），extra_bslash = true 表示标号 i 代表的字符在输出的时候需要加反斜杠 "\\"（在使用正则表达式定义的规则中，"+|-|*|/" 需要用转义符写作 "\+|\-|\*|\/"，因为这些符号在正则表达式中有具体意义；需不需要加双反斜杠取决于Python的正则表达式规则）。
（UPD：讲个笑话，实际测试下来，C语言子集的保留字比 MIPS汇编的保留字简单好多，甚至可以手动避免前缀冲突）
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211111095136797-328935327.png" alt="" width="466" height="123" loading="lazy">
 
7. 匹配优先级（Token 内）
Token 内的优先级指的是正则表达式内部的模式串互为前缀时，应当优先匹配哪个。比如存在两种类型 "longlong" 与 "long"（之前说过了 ply.lex 不能匹配带空格的规则 "long long"），而我们想用同一个规则 t_LONG_INT 来匹配。
对于这种情况，我们需要把较长的串写在前面、较短的串写在后面，即：
<div class="cnblogs_code">
<pre>def t_LONG_INT(t):
r"""longlong|long"""
return t</pre>
</div>
 在这种情况下，即使匹配上了 "long"、而在匹配 "longlong" 的过程中失败了（比如文本为 "longdouble"），仍然会正确地返回 "long"，并且在 "long" 之后接着匹配；而如果将匹配规则写作 r"""long|longlong"""，当目标串为 "longlong" 时则会返回两个 "long"，就不是预期的结果了。
 
8. 函数方式定义支持的操作
上面说到函数方法定义的规则支持相对比较复杂的操作，这里就挑两个例子说明一下。
(1) 维护当前行号
ply.lex 本身是不会维护行号的（毕竟在一些语言中，"\n" 是应该被放进 t_ignore 中的），所以需要在扫到文本中的 "\n" 时维护 lexer.lineno：
<div class="cnblogs_code">
<pre>def t_ENDL(t):
r"""\n+"""
t.lexer.lineno += len(t.value)
return t</pre>
</div>
(2) 与全局变量联动（例子：统计单词数）
<div class="cnblogs_code">
<pre>token_1_cnt = 0

def t_TOKEN_1(t):
r"""token_1"""
global token_1_cnt
token_1_cnt += 1
return t</pre>
</div>
(3) 修改返回信息
在下一节返回值中细讲。
 
9. 匹配规则的返回值
在之前的函数方式定义中，我们都在最后写上了 return t（t 为 Token 类型），不过并没有说明它的用途；而在字符串方法中甚至完全不显式地产生返回值（其实内部实现也只是单纯地 return t）。现在我们来进一步分析返回值的机制和作用。
return t 到底被用到哪里去了，如果不返回会有什么后果？本着这样的思路，我们采用函数方法定义如下的规则，并将 return t 删去：
<div class="cnblogs_code">
<pre>def t_TOKEN(t):
r"""token"""</pre>
</div>
然后用文本 data = 'token' 进行词法分析，结果会报错，信息如下：
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211108170019440-1027366239.png" alt="" width="867" height="107" loading="lazy">
定位到错误抛出的地点，发现代码段的注释信息为 "No match. Call t_error() if defined."。可以看出如果不将 t 返回，Lex 就会认为没有匹配上规则。
通过进一步分析（比如修改 t.value 并输出），我们能够发现，返回的 t 不仅是 lexer.token() 所获得的 Token，t.value 更会出现在 Yacc 的语法分析中（而 t.type、t.lineno 和 t.lexpos 则在语法分析时不会保留，详见 Yacc 部分的第5小节）。所以，我们不仅有必要将 t 返回，还可能需要将重要的信息额外保存在 t.value 中（比如 t.type，或是其他一些标记）。
我们可以自由地选择 t.value 中保存的信息格式，Python中独特的List类型是一个不错的选择：
<div class="cnblogs_code">
<pre># 这里仅给出了关键代码
def t_VALUE(t):
r"""(0+)|(+)|(+)"""
t.value =
return t

data = '0x233'</pre>
</div>
运行后的 Token 输出结果为：
<div class="cnblogs_code">
<pre>> LexToken(VALUE,['VALUE', '0x8c'],1,0)</pre>
</div>
 
10. 一些可能有用的东西
官方文档中还介绍了一些我觉得有用的特性，不过我没有用过，如果有需求可以自行阅读。
官方文档4.12 - the @TOKEN decorator：关于如何用 docstring 作为匹配规则；
官方文档4.15 - alternative specification of lexers：关于如何将 lexer 封装进自定义类中；
官方文档4.19 - conditional lexing and start conditions：大概是允许在多种匹配模式中切换？有点没看懂。
 
<hr>
 
Yacc
 
1. 简单介绍
ply 包提供的 Yacc 工具能够对于给定的文本进行语法分析。Yacc 采用类似 .y 文件的格式表示产生式，而我们需要给定这些产生式。
与 Lex 工具能够获得 Token 序列不太一样，如果只使用最基本的 Yacc 只能够检查词法分析后的 Token 序列是否满足给定的语法规则，并没有什么输出。Yacc 真正强大的地方在于完成模式匹配后，能够方便地确定每个 Token 在模式串中的角色，从而能够在基础语法检查的基础上稍加修改就能进行更高层级的检查（比如检查变量的未定义/重定义）以及高级语言向低级语言的转化。
 
2. 基本结构
按照功能来分类的话，整个 ply Yacc 的代码（不含 Lex 部分以及主函数内）分为如下两个部分（细节在之后会展开说）：
<div class="cnblogs_code">
<pre># 1. 包的引入
from ply import yacc

# 2. Production匹配规则的声明
start = 'production'# 默认的起始产生式为p_start，可以通过给start赋值来修改为p_production

def p_production(p):
r"""production : TOKEN_1
 | production TOKEN_2"""</pre>
</div>
主函数的调用如下所示，需要显式地定义 lexer，但不需要向其中喂文本：
<div class="cnblogs_code">
<pre>if __name__ == '__main__':
data = '0x233'

lexer = lex.lex()
parser = yacc.yacc(debug=True)
parser.parse(data)</pre>
</div>
如果没有 Token 能接收十六进制数的话，就会产生形如下面的 Lex 报错信息（匹配不到合适的词，词法分析失败）：
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211108205208985-1566227451.png" alt="" width="916" height="167" loading="lazy">
如果有 Token 能接受十六进制数、但不是 TOKEN_1 时，就会产生形如下面的 Yacc 报错信息（根据产生式可知，production 的开头必须为 TOKEN_1）：
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211108205801714-1576718727.png" alt="" width="357" height="47" loading="lazy">
如果 TOKEN_1 可以接收十六进制数的话，就会产生形如下面的运行成功信息：
<img src="https://img2020.cnblogs.com/blog/1546407/202111/1546407-20211108204650093-1842352229.png" alt="" width="350" height="121" loading="lazy">
除了一堆 WARNING 以外就是生成 LALR table 的提示（这句提示在对于同一份规则第二次运行时就没有了），之后啥输出都没有，所以往往需要采用后文介绍的方法通过输出产生式的信息来进行debug。
 
3. Production 匹配规则的声明
Production 匹配规则只有函数声明的方式，函数的名称为 "p_" + 产生式名称，且产生式的左项需要与产生式名称相同。产生式的名称不需要像 Token 名称一样预先写在列表中。
当只有一个产生式时，raw string的格式为：
<div class="cnblogs_code">
<pre>r"""production_name : token_name_1 production_name_2"""</pre>
</div>
当有多个产生式时，需要换行后写在 "|" 符号的后面：
<div class="cnblogs_code">
<pre>r"""production_name : token_name_1 token_name_2
 | production_name token_name_3
 | token_name_4"""</pre>
</div>
为了与词法分析得到的 Token 区分，Production 的名称一般定义为全小写字母。
另外需要特别注意的是，假如产生式中需要递归，那么必须采用左递归。以下是一个简单的表达式的例子：
<div class="cnblogs_code">
<pre>def p_expr(p):
r"""expr : expr OPERATOR NUMBER
 | NUMBER"""</pre>
</div>
这里再给出一个画风比较正常的 Production 匹配规则的声明：
<div class="cnblogs_code">
<pre>def p_if(p):
r"""if : IF LBRACKET TRUE RBRACKET
 | IF LBRACKET FALSE RBRACKET
 | IF LBRACKET expr BRACKET"""</pre>
</div>
这个匹配规则给出了一个简化的C++中 if 语句条件的语法规则。其中 IF 匹配保留字 "if"，LBRACKET 匹配左括号 "("，RBRACKET 匹配右括号 ")"，TRUE 匹配保留字 "true"，FALSE 匹配保留字 "false"，expr 匹配一个产生表达式的 Production。
 
4. 特殊的匹配规则
要说 Yacc 中比较特殊的匹配规则，大概只有 p_empty 了。p_empty 就是一般意义上的 $\epsilon$，定义方法如下：
<div class="cnblogs_code">
<pre>def p_empty(p):
"""empty :"""
pass</pre>
</div>
那么一个 $\mathrm{production}\rightarrow \epsilon$ 的产生式就可以写作：
<div class="cnblogs_code">
<pre>def p_production(p):
r"""production : empty"""</pre>
</div>
 
5. Production 类型的组成与使用
在我们声明 Production 的匹配规则时，传入了一个参数 p。这个参数是我们获得该完成匹配的模式串的唯一途径。
p 是一个长度不固定的 List，实际长度等于 匹配上的产生式长度 + 1（因为当前产生式名称作为左项占据了 p）。举个例子：
<div class="cnblogs_code">
<pre>def p_production(p):
r"""production : TOKEN_1 production_2 TOKEN_2
 | TOKEN_3"""
# ^ ^ ^ ^
# p p p p</pre>
</div>
假如产生式 production 的匹配结果是 TOKEN_1 production_2 TOKEN_2，那么 List 的长度为 4；假如匹配结果是 TOKEN_3，那么 List 的长度为 2。
p 里面装的是什么东西呢？对于 Token 而言，p 的值就是 Token.value，而 Token.type 的信息都被丢掉了（这个在介绍 Token 匹配规则的返回值时提到过）；而对于 Production 而言，如果不做任何操作，p 的值是 None。如果想让此时代表 production_2 的 p 有值，我们就需要在 production_2 的匹配规则 p_production_2 中为 p 赋值。示例如下：
<div class="cnblogs_code">
<pre>def p_production_2(p):
r"""production : empty"""
p = ['production_2', 'empty']</pre>
</div>
因为 Yacc 的匹配是一个递归的过程，所以当我们完成了 production 的匹配时，一定在此之前也完成了 production_2 的匹配，所以此时的 p = ['production_2', 'empty']。
知道了 p 是什么东西以后，对于有多个产生式的 Production，我们可以通过分类讨论 len(p) 的大小以及具体某个 p 的值来加以区分。访问和操作也与正常操作 List 没什么区别。
由于 p 是一个 List，所以我们可以往 p 里塞任何东西。不过如果要塞多个属性的话，最好用 List 装起来便于操作。
除了 List 中的内容以外，Production 还支持获取 Token.lineno 和 Token.lexpos，使用方法为 p.lineno(i) 和 p.lexpos(i)。还有一些细节有需要的话可以参考官方文档6.9 - line number and position tracking。
 
6. 匹配完成后的进阶操作
一时半会并不能想起来什么太高端的操作...就拿表达式求值和检查变量是否未定义/重定义来说一说吧。
(1) 表达式求值
这个是官方文档中描述的例子，其实整体思路很简单：对于 Token，将 Token.value 转为 int 类型；对于 Production，根据运算的类型（通过检查运算符对应的 p 的值加以分辨）执行相应的运算，将结果赋给 p 即可。
为了简单起见，只实现操作符为加减的表达式求值，更加复杂的表达式需要根据运算优先级设计 Production 的匹配规则，这里就不展开说了。
<div class="cnblogs_code">
<pre>from ply import lex, yacc

tokens = (
'NUMBER', 'PLUS', 'MINUS'
)

t_PLUS = r"""\+"""
t_MINUS = r"""\-"""
t_ignore = ' \t'

def t_NUMBER(t):
r"""+"""
t.value = int(t.value)
return t

start = 'expr'

def p_expr(p):
r"""expr : NUMBER
 | expr PLUS NUMBER
 | expr MINUS NUMBER"""
if len(p) == 2:
 p = p
elif p == '+':
 p = p + p
else:
 p = p - p

if __name__ == '__main__':
data = '1+2-3+4-5'

lexer = lex.lex()
parser = yacc.yacc(debug=True)
print(parser.parse(data))

# 运行结果：-1</pre>
</div>
(2) 检查变量定义
这是在写课设时碰到的问题，实现起来也并不困难。在全局维护一个 Dict，当完成变量的定义时就检查 Dict 中是否已有该变量名，从而检查是否重定义；当使用到某个变量时，同样在 Dict 中检查该变量名，从而检查是否未定义。
因为只是展示一下思路，所以对于语法做了很多简化，通过 define 来定义变量，在表达式中使用变量。
<div class="cnblogs_code">
<pre>from ply import lex, yacc

tokens = (
'VARIABLE', 'NUMBER',
'DEFINE', 'PLUS', 'MINUS', 'ENDL'
)

t_PLUS = r"""\+"""
t_MINUS = r"""\-"""
t_ignore = ' \t'

def t_DEFINE(t):
r"""define"""
return t

def t_VARIABLE(t):
r"""*"""
t.value = ['VARIABLE', t.value]
return t

def t_NUMBER(t):
r"""+"""
t.value = ['NUMBER', t.value]
return t

def t_ENDL(t):
r"""\n+"""
t.lexer.lineno += len(t.value)
return t

start = 'codes'
dict_variable = {}

def p_codes(p):
r"""codes : code
 | codes ENDL code"""

def p_code(p):
r"""code : expr
 | define"""

def p_define(p):
r"""define : DEFINE VARIABLE"""
if p in dict_variable:
 raise Exception('redefined {} at line {}'
 .format(p[2], p.lineno(2)))
else:
 dict_variable] = p.lineno(2)

def p_expr(p):
r"""expr : NUMBER
 | VARIABLE
 | expr PLUS NUMBER
 | expr PLUS VARIABLE
 | expr MINUS NUMBER
 | expr MINUS VARIABLE"""
if p == 'VARIABLE':
 if p not in dict_variable:
 raise Exception('undefined {} at line {}'
 .format(p, p.lineno(2)))
 
if __name__ == '__main__':
data = r"""define x
 define a
 x + a + 4 + b"""

lexer = lex.lex()
parser = yacc.yacc(debug=True)
print(parser.parse(data))

# 报错信息：Exception: undefined b at line 3</pre>
</div>
 
7. 产生式中简单符号的简化写法
在实际情况中，很多 .y 文件中的产生式长这个样子：
<div class="cnblogs_code">
<pre>additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
;</pre>
</div>
像 '+'、'-' 这些长度为1的简单符号（如果长度不为1，则需要通过词法规则来定义，比如 '=='），如果我们必须分别定义 t_PLUS、t_MINUS 等 Token 的话，就稍微显得有些麻烦——在产生式规则中，这些简单符号的出现并不会引起歧义，并且绝大多数现成的 .y 文件都是采用了上面的简化写法。
对于上面的规则，我们可以这样改写成 Production 匹配规则：
<div class="cnblogs_code">
<pre>def p_additive_expression(p):
r"""additive_expression : multiplicative_expression
 | additive_expression '+' multiplicative_expression
 | additive_expression '-' multiplicative_expression"""
if len(p) == 4:
 if p == '+':
 p = p + p
 if p == '-':
 p = p - p</pre>
</div>
不过，对于所有在产生式中使用到的简单符号，我们需要将他们包含在 literals 中：
<div class="cnblogs_code">
<pre>literals = ['+', '-']</pre>
</div>
使用 literals 规则，获得的 Token 的 Token.type 与 Token.value 均为符号本身（类型为 str）。
使用这种简化写法，我们可以重写上一节中表达式求值的代码：
<div class="cnblogs_code">
<pre>from ply import lex, yacc

tokens = (
'NUMBER',
)

t_ignore = ' \t'
literals = ['+', '-']

def t_NUMBER(t):
r"""+"""
t.value = int(t.value)
return t

start = 'expr'

def p_expr(p):
r"""expr : NUMBER
 | expr '+' NUMBER
 | expr '-' NUMBER"""
if len(p) == 2:
 p = p
elif p == '+':
 p = p + p
else:
 p = p - p

if __name__ == '__main__':
data = '1+2-3+4-5'

lexer = lex.lex()
parser = yacc.yacc(debug=True)
print(parser.parse(data))
# 运行结果：-1</pre>
</div>
 
8. 一些可能有用的东西
官方文档6.6 - dealing with ambiguous grammars：一般来说ambiguous grammer会导致产生shift-reduce或者reduce-reduce冲突，是应当尽量避免的。不过 ply.yacc 支持通过规定优先级的方式来避免这些冲突。
官方文档6.8 - syntax error handling：更加高阶的语法错误检测，不会像目前的做法一样遇到任何错误就终止。不过需要设置不少东西。
官方文档6.11 - embedded actions：算是一个trick吧，可以在语法分析的过程中输出中间信息。为什么这样说起来感觉就很trivial...
 
<hr>
 
牡蛎~ 感觉身体被掏空
感觉自己的contribution主要在于 Lex 那边变量名避免撞保留字前缀的代码生成，看了一遍document应该是没有处理吧...如果里面直接解决了就显得我很蠢了...
（完） 
来源：https://www.cnblogs.com/LiuRunky/p/Python_Ply_Tutorial.html

頁: [1]

琼殿技术论坛's Archiver

Python ply包的正确食用手册