网站网络营销中山百度关键词搜索

本文是5分钟理解CFG上下文无关文法的续集，在5分钟理解CFG上下文无关文法这篇文章中已经讲解了CFG的基本概念，但是CFG的解析算法才是核心。由于它的解析算法极其复杂，网上很少有文章能把解析算法用大众能理解的语言写出来，本人在理解了算法后用python代码实现了算法，通过测试用例验证了该算法的正确性，当然也验证了我理解的是正确的。

这里说的解析其实就是验证一个输入字符串input是否符合给定的文法G，实现算法有CYK解析算法，和Eerley解析算法，都是是以人名命名。下面介绍Eerley解析算法

假设input的字符串是” 2021年2月1日”,验证是否符合下面定义的日期类文法，下面竖线|表示“或”，DIG0_9->ZERO | DIG1_9 实际上等价于2条规则：DIG0_9->ZERO；DIG0_9->DIG1_9。#后面是注释。

S->Y M D  #year month day
Y->YN YT  #YN:year number;YT:year tag
YT->"年"
M->MN MT #MN:month number; MT:month tag
MN-> DOZEN  #1 到12
MT->"月"
DT->"日"
YN->DIG1_9   DIG0_9  DIG0_9  DIG0_9  # DIG1_9:digit 1