★ FEATURED ARTICLE 简介这份西南科技大学编译原理实验报告1面向计算机专业学生及刚接触编译器前端的学习者聚焦“设计词法分析程序”实验任务帮助读者理解从正则表达式到NFA、DFA确定化与最小化的完整流程并完成TEST语言单词分类与输出方案设计。包内为1个doc文档约444KB涵盖实验目的、实验设计、实验过程与程序实现结合Python状态机框架展示词法分析程序的组织方式也提示错误处理、缓冲区管理与回溯等工程细节。已有477人学习适合用于实验报告撰写参考、编译原理课程复习及词法分析模块对照实现可据此梳理DFA状态转移表与单词输出格式为后续语法分析打下基础。1. 一份词法分析实验报告从正则到 lex.txt 的完整链路某高校《编译系统综合设计》的实验报告一题目是设计词法分析程序把正则表达式 → NFA → 确定化 → 最小化 DFA → Python 扫描器 → lex.txt 输出这条链路完整走了一遍还附了调试记录和两道讨论题。它解决的是一个很具体的尴尬编译原理课讲了三周自动机理论实验课却要求交一份能跑的扫描器中间那段落差没人补。适合赶编译原理实验报告的学生、想把书里那张手画状态图变成可执行代码的自学者以及要手写一个配置式 lexer 的工程师。陷阱也很明确——报告里贴的 Python 代码状态转移表和前面画的 DFA 根本不是同一台机器直接抄会翻车。下面按理论到实现的顺序拆。2. 正则表达式与 NFATEST 语言七类词怎么表达成自动机这一章解决的是规则怎么写和规则怎么变成状态机两件事。很多人卡在第一步不是因为不会写正则而是没想清楚正则和自动机之间那条通道——Thompson 构造法就是这条通道它保证任何正则表达式都能机械地翻译成 NFA不需要灵感。2.1 七条词法规则的正则写法与冲突处理TEST 语言在报告里定义了七类词标识符、关键字保留字、无符号整数、分界符、运算符、注释符加上被跳过的空白。把它们写成正则不难难的是这些正则之间存在大量重叠必须先定好切分顺序。类别正则表达式说明标识符 ID[A-Za-z][A-Za-z0-9]*报告用(a|b|…|z|A|B|…|Z)(0|1|…|9|a|…|Z)*展开写法无符号整数 NUM0 | [1-9][0-9]*严格写法排除前导零实操里经常放宽关键字 KEYWORDint|if|else|while|for|do|read|write不单独建自动机扫出 ID 后查表分界符 DELIM{ | } | ( | ) | ; | , | :单字符直接一条边运算符 OP | - | * | / | | | | | | | !注意双字符优先注释 COMMENT//[^\n]*不产生 token只吞字符空白[ \t\r\n]跳过但要用来维护行号表里有四处冲突必须在设计阶段就拍板否则后面全是补丁。第一处是关键字和标识符。教科书做法是给if、while各建一条独立分支结果是 NFA 里凭空多出几十个状态最小化之后还是几十个。主流编译器的做法是根本不区分int在词法层就是一个合法标识符扫完之后拿字符串去哈希表里查一次命中就改类型。这样 DFA 里只需要一条ID状态工程量和可维护性差一个数量级。第二处是/和//。单个/是除号两个连着是注释开头。这不是靠优先级声明能解决的只能靠最长匹配——读到第一个/时先接受为除号候选再看下一个字符是/就继续走注释分支。第三处是和、和、!和!。同样是最长匹配单独出现时是合法运算符后面跟时才升格成。这意味着对应的状态既是接受态又有出边——这是整个 DFA 里最容易写错的结构后面第 5 章会专门讲。第四处是注释。从词法角度看注释不是单词但它必须被正确吞掉而且吞的时候要维护行列号否则报错位置全错。提示报告里int同时被列进关键字和保留字两个分类这是原始材料的口径含混不是两种不同的东西。实现时统一按关键字处理即可不用为它单独建类别。2.2 Thompson 构造从正则到 NFA 的四条拼装规则正则表达式到 NFA 的转换是纯机械的只有四条规则任何复杂的正则都是这四条规则递归拼出来的。单字符c新开两个状态 s、es 上加一条读c到 e 的边。连接RSR 的所有接受态加 ε 边指向 S 的初态R 的初态成为新初态S 的接受态成为新接受态。选择R|S新开一个初态用两条 ε 边分别指向 R 和 S 的初态再新开一个接受态R 和 S 的所有接受态用 ε 边指向它。闭包R*新开初态ε 边一条指向 R 初态、一条直接指向新接受态R 的每个接受态用 ε 边回指 R 初态同时指向新接受态。把这四条规则写成代码数据结构只需要两个字段转移表和接受态集合。转移表的键是(状态, 字符)字符用None表示 ε 边。# NFA 的最小表示转移表 初态 接受态接受态带 token 类型便于后续合并 class NFA: def __init__(self): self.trans {} # (state, ch) - set(state)chNone 表示 ε 边 self.start None self.accept {} # state - token 类型字符串 def add(self, src, ch, dst): self.trans.setdefault((src, ch), set()).add(dst) _seq [0] def new_state(prefixs): _seq[0] 1 return f{prefix}{_seq[0]} def frag_char(c): 单字符片段s --c-- e n NFA() s, e new_state(), new_state() n.start s n.accept {e: None} n.add(s, c, e) return n def _union_env(*frags): 把多个 NFA 的状态和边并到一个新对象里供下面三条规则复用 n NFA() for f in frags: for k, v in f.trans.items(): n.trans.setdefault(k, set()).update(v) n.accept.update(f.accept) return n def frag_concat(a, b): 连接 RSa 的每个接受态打 ε 边指向 b 的初态 n _union_env(a, b) n.start a.start n.accept dict(b.accept) # 连接后只有 b 的接受态有效 for s in a.accept: n.add(s, None, b.start) return n def frag_alt(a, b): 选择 R|S新初态分两路两路接受态汇到新终态 n _union_env(a, b) s0, e0 new_state(s), new_state(s) n.start s0 n.add(s0, None, a.start) n.add(s0, None, b.start) n.accept {e0: None} for s in list(a.accept) list(b.accept): n.add(s, None, e0) return n def frag_star(a): 闭包 R*接受态回指初态同时 ε 跳过整个片段 n _union_env(a) s0, e0 new_state(s), new_state(s) n.start s0 n.add(s0, None, a.start) n.add(s0, None, e0) for s in a.accept: n.add(s, None, a.start) n.add(s, None, e0) n.accept {e0: None} return n这段代码的逻辑很直白但有三个参数含义需要说清楚否则抄完改不动。self.trans用(状态, 字符)元组做键而不是嵌套字典是因为 ε 边没法用字符索引用None当字符是最省事的做法后面求 ε-闭包时直接取trans.get((s, None), set())就行。self.accept从set改成了dict值存 token 类型。原因在后面合并阶段多条规则拼成一台机器后必须知道停在哪个接受态对应哪种词否则还得反过来查状态编号。用None占位表示这是接受态但还没定类型合并时统一填充。_seq是全局计数器保证两条并行构造的片段不会撞状态名。工程实现里一般会换成带前缀的命名空间或者直接给每个 NFA 分配独立编号段这里用全局自增是为了代码短。用这四条规则拼一条标识符的正则[A-Za-z][A-Za-z0-9]*写法是# 26 个小写 26 个大写用选择串起来 letter frag_char(a) for c in bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ: letter frag_alt(letter, frag_char(c)) digit frag_char(0) for d in 123456789: digit frag_alt(digit, frag_char(d)) ident frag_concat(letter, frag_star(frag_alt(letter, digit)))手工拼 60 多条|显然不现实实际项目里这一段一定是先用正则解析器把字符串解析成语法树再递归下降或者干脆直接手写状态机跳过 NFA 阶段。做实验报告时手工拼一遍是有意义的因为拼完你会发现frag_star里那两条 ε 边到底指向哪里这件事画图容易画错。2.3 合并 NFA一个新初态把七条规则接成一台机器每条规则单独构造出来的 NFA 是七台互不相干的机器它们各自有初态、各自有接受态。要变成一台能同时识别所有词的扫描器需要做一次合并新建一个总初态 S用 ε 边分别指向七个子片段的初态把所有子片段的接受态保留并标注上各自的 token 类型。def build_combined_nfa(rules): rules: [(token_type, 子NFA), ...]返回一台合并后的 NFA n NFA() n.start new_state(S) for ttype, frag in rules: for k, v in frag.trans.items(): n.trans.setdefault(k, set()).update(v) n.add(n.start, None, frag.start) # 总初态 ε 边分叉 for s in frag.accept: n.accept[s] ttype # 接受态打上 token 类型 return n RULES [ (ID, ident), (NUM, frag_concat(frag_char(0), frag_star(digit))), # 简化版允许前导零 (OP, frag_alt(frag_char(), frag_char())), # 其余运算符同理拼接 (DELIM, frag_char(;)), (COMMENT, frag_concat(frag_char(/), frag_char(/))), # 注释体在扫描阶段吞掉 ] combined build_combined_nfa(RULES)合并这一步有两个容易忽略的细节。第一个是总初态必须新建不能拿某条规则的初态顶替。因为int这条规则和标识符规则的初态是不同的如果复用其中任何一个另外六条规则的入口就断了扫出来的结果会漏词。第二个是接受态的标注时机。合并前每个子片段都是{e: None}合并时统一填ttype。如果某条规则内部用了frag_alt它的接受态经过_union_env之后还是None会被build_combined_nfa补上顺序不能反——先并转移、再打标签否则标签会被覆盖。合并后的 NFA 状态数通常在 100 到 300 之间取决于正则的展开程度。这个数字本身没意义因为它马上就要被确定化成 DFA状态数会变边数也会变。但它决定了确定化阶段的表有多大——子集构造的复杂度是 O(2^n)所以 NFA 设计得越紧凑后面越省事。这也是为什么前面强调不要把关键字单独建成 8 条分支那会让 NFA 的初始状态直接多出 8 个分支点子集构造时状态爆炸的概率显著上升。还有一点值得说注释符//在合并 NFA 里只构造了两个字符的片段完整的注释体[^\n]*没进去。这是有意为之。注释体是任意长度、任意字符把它塞进 DFA 只会让状态转移表多出一大堆到行尾的自环而它对 token 输出没有任何贡献。工程上的通行做法是DFA 只负责识别//这个开头识别到之后立刻切换到行注释模式用一段简单循环吞到换行符为止。报告里的代码在这一点上是混着处理的后面第 5 章会展开。3. 确定化与最小化子集构造和 Hopcroft 划分的手算过程NFA 是不能直接跑的因为同一个状态读同一个字符可能有多条出边程序无法决定走哪条。确定化的任务就是把它变成一台每个状态每个字符最多一条出边的机器代价是状态数可能指数膨胀。最小化再把膨胀出来的冗余状态合并回去。3.1 子集构造ε-闭包和 move 两个原语子集构造的核心思想是DFA 的每一个状态对应 NFA 状态集合的一个子集。读一个字符就把当前子集能到达的所有状态收集起来再求一次 ε-闭包得到下一个子集。需要两个原语。ε-闭包从一个状态集合出发沿着所有 ε 边能走到的全部状态含起点自身。move从一个状态集合出发读一个具体字符能到达的全部状态不含 ε 展开。def eps_closure(states, trans): 沿 ε 边做可达性扩展返回闭包后的 frozenset stack list(states) seen set(states) while stack: s stack.pop() for t in trans.get((s, None), ()): if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def move(states, ch, trans): 读一个字符后能到达的状态集合不展开 ε out set() for s in states: out | trans.get((s, ch), set()) return out def determinize(nfa): 子集构造NFA - (状态编号表, 转移表, 接受类型表) alphabet sorted({c for (_, c) in nfa.trans if c is not None}) start eps_closure({nfa.start}, nfa.trans) id_of {start: 0} order [start] trans {} # (dfa_state_id, ch) - dfa_state_id accept {} # dfa_state_id - token 类型 queue [start] while queue: cur queue.pop(0) cid id_of[cur] for ch in alphabet: nxt eps_closure(move(cur, ch, nfa.trans), nfa.trans) if not nxt: continue if nxt not in id_of: id_of[nxt] len(order) order.append(nxt) queue.append(nxt) trans[(cid, ch)] id_of[nxt] # 该子集里只要含 NFA 接受态DFA 状态就是接受态 types {nfa.accept[s] for s in cur if nfa.accept.get(s)} if types: accept[cid] sorted(types)[0] # 冲突时按优先级取见下方说明 return order, trans, accept代码里queue是待处理的子集队列用列表 pop(0) 实现广度优先。生产代码会换成collections.deque因为 list 的 pop(0) 是 O(n)几千个状态时会有明显感知。types取集合而不是单个值是因为一个子集里可能同时含有两个不同 token 类型的 NFA 接受态。这种情况说明词法规则本身有歧义比如int如果单独建了分支扫到i的时候那个子集里既有 ID 的接受态路径也有 int 的接受态路径。处理办法有两种一是靠最长匹配在扫描阶段自然消解in不是int长度不够二是给sorted(types)[0]定一个明确的优先顺序。我一般会显式写一个TYPE_PRIORITY [KEYWORD, ID, NUM, OP, DELIM]的字典用min(types, keyTYPE_PRIORITY.index)取比sorted靠谱因为字符串排序是字典序跟业务优先级无关。手算的时候会画一张表行是 DFA 状态也就是 NFA 子集列是字母表里的每个字符格子里填 ε-闭包后的新子集。这张表要一直填到没有新子集产生为止。闭包符号用ε-closure({...})表示子集直接写状态编号集合比如{1,2,5}。填表时有个技巧先把含初态的子集ε-closure({S})写在第一行然后逐个字符展开新出现的子集编号往后排这样不会漏。3.2 最小化按 token 类型做初始划分确定化得到的 DFA 通常有一半状态是冗余的最小化的目标是在保持语言不变的前提下把状态数压到最少。Hopcroft 划分法的思路是先把状态分成接受态和非接受态两组然后反复检查每组内部能不能再按读同一个字符后落到哪一组细分直到划分不再变化。def minimize(n_states, alphabet, trans, accept, start): def group_of(part, s): for i, g in enumerate(part): if s in g: return i return -1 # 初始划分相同 token 类型的接受态一组非接受态单独一组 buckets {} for s in range(n_states): buckets.setdefault(accept.get(s), set()).add(s) part list(buckets.values()) while True: new_part [] for g in part: sig {} for s in g: # 签名读每个字符后落到哪个组 key tuple(group_of(part, trans.get((s, ch), -1)) for ch in alphabet) sig.setdefault(key, set()).add(s) new_part.extend(sig.values()) if len(new_part) len(part): break part new_part # 重新编号输出最小 DFA new_trans, new_accept {}, {} for i, g in enumerate(part): rep next(iter(g)) if rep in accept: new_accept[i] accept[rep] for ch in alphabet: t trans.get((rep, ch)) if t is not None: new_trans[(i, ch)] group_of(part, t) return len(part), new_trans, new_accept, group_of(part, start)初始划分用accept.get(s)做键意味着接受态按 token 类型分组、非接受态归为一组。如果用传统的二划分接受态一组、非接受态一组最小化出来的状态数会多一些因为不同 token 类型的接受态在后续迭代中还是会被拆开只是多绕几轮。直接按类型分更省事也更贴近词法分析的实际需求。trans.get((s, ch), -1)里的-1是死亡状态的占位。DFA 里没有显式死亡状态时缺边就是死亡用-1表示group_of会返回-1所有缺边的状态在这个字符上签名相同自然归到一起。代码里part是列表的列表group_of用线性扫描找组号。状态数上千时这会变成瓶颈实际实现会用dict维护state - group_id的映射每轮重建一次。实验报告规模下几十个状态无所谓。最小化之后状态数通常能压到 10 到 20 之间。这个量级刚好可以画在一张 A4 纸上也刚好可以手写进制表里。3.3 把结果落成状态转移表最小化得到的new_trans是以整数状态编号为键的直接塞进扫描器可读性很差。落地时要做一次重命名把状态改成有意义的字符串把字符按类别归并最终得到一张人能看懂的转移表。字符归并有讲究。字母有 52 个如果每个都单独一列转移表会有 52 列冗余而且每一列的走向完全相同。归并成类别L字母、D数字、其余字符保持原样表就从 70 列压到 20 列左右。def to_class(ch): if ch.isalpha(): return L if ch.isdigit(): return D return ch def rebuild_table(new_trans, alphabet, rename): 把整数编号的 DFA 表转成人能读的字符串表 table {} for (s, ch), t in new_trans.items(): cls to_class(ch) table.setdefault(rename[s], {})[cls] rename[t] # 同一状态同一类别必须映射到同一目标否则归并失败 for s, row in table.items(): for cls, t in row.items(): pass return table这段代码的重点不是实现而是那个注释——归并字符类别时有一个隐含前提同一状态下所有被归到同一类的字符转移目标必须相同。字母归成L是安全的因为标识符状态读任何字母都还在标识符状态但如果把和混着归并就会出错。落地前建议加一句断言先用原表逐字符展开检查同类字符的目标是否一致不一致就不归并单独留一列。最终得到的那张表就是第 4 章扫描器的输入。手工整理出来的版本大致长这样S是初态ID、NUM、GT、GE等是状态名L/D是归并后的字符类其余字符原样作为键。这张表同时包含了接受信息——哪些状态是接受态、接受成什么 token单独用一张字典维护。这两张表加起来不到 40 行比一个几百行的if-elif链好维护得多。4. 从 DFA 表到 Python 扫描器最长匹配、回退和词法错误定位理论部分到这里就结束了。这一章是整份资源的实操核心把第 3 章那张表喂给一个循环让它吐出 token 序列、写进lex.txt同时把非法字符的行列号报出来。4.1 表驱动主循环最长匹配靠一个 last 指针兜底扫描器的骨架非常固定从当前位置出发尽可能多地读字符每读一个就查表跳状态记录最后一次停在接受态的位置读不下去时回退到那个位置切出一个 token。关键在于那个最后一次接受态的记录。以为例读到时状态是GT这是个接受态记下位置再读状态变成GE也是接受态更新记录如果后面是字母读不动了回退到GE的位置切出。如果只读到就读不动了回退到GT的位置切出。# DFA 状态转移表等价于第 3 章最小化后的结果状态名做了可读化处理 TRANS { S: {L: ID, D: NUM, : GT, : LT, : ASSIGN,!: NOT, /: DIV, : PLUS, -: MINUS, *: STAR, (: LPAREN,): RPAREN, {: LBRACE,}: RBRACE,;: SEMI, ,: COMMA, :: COLON}, ID: {L: ID, D: ID}, NUM: {D: NUM}, GT: {: GE}, # 本身是接受态且还能继续吃 LT: {: LE}, ASSIGN: {: EQ}, NOT: {: NE}, # 单独的 ! 不是合法 token DIV: {/: COMMENT}, # 除号状态吃到一个 / 就转注释 } ACCEPT { ID: ID, NUM: NUM, GT: OP, GE: OP, LT: OP, LE: OP, EQ: OP, NE: OP, ASSIGN: OP, PLUS: OP, MINUS: OP, STAR: OP, DIV: OP, LPAR p a hrefhttps://download.csdn.net/download/m0_65436422/88754609 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p
阅读完成 · 觉得有帮助？
