如何编写满足指定字符串构成及次数约束的BNF语法规范
符合要求的BNF语法编写方案
首先明确目标语言的形式化规则:
- 合法字符串基础结构:连续
x串、连续y串、连续z串依次拼接,即形如x^a y^n z^b,其中a≥0为x的出现次数,b≥0为z的出现次数,n≥0为y的出现次数 - 强制计数约束:
n > a + b,即y的出现次数严格大于x和z的出现次数之和
朴素BNF的局限性
如果直接用常规连续串写法编写BNF,是无法实现计数约束的,示例如下:
<S> ::= <Xs> <Ys> <Zs> <Xs> ::= 'x' <Xs> | ε <Ys> ::= 'y' <Ys> | ε <Zs> ::= 'z' <Zs> | ε
上述写法仅能匹配所有符合x*y*z*结构的串,但经典BNF本身是上下文无关的,不支持跨非终结符的数量比较或算术运算,无法直接表达y的数量必须多于x+z之和的要求,需要通过构造递归非终结符实现计数匹配逻辑。
正式BNF实现
构造核心逻辑
- 每在串开头新增1个
x,或在串结尾新增1个z,就需要在中间的y块中预留1个y的匹配额度,用于平衡x/z的计数 - 当停止新增x、z进入纯y块生成阶段时,预留的匹配y全部生成完成后,必须额外生成至少1个y,才能满足"严格大于"的约束
- 所有x仅出现在串开头、所有z仅出现在串结尾、所有y仅在中间连续出现,保证基础结构符合要求
非终结符说明
通过非终结符的下标标识当前需要匹配的计数状态:
S:开始符号,初始计数额度为0,代表暂无需要补偿的x/z计数S_m:累计了m个需要补偿的x/z计数,可以继续新增x或z,也可以进入y块生成阶段Y_m:进入y块生成阶段,当前累计m个需要匹配的y,生成完这部分匹配的y后,必须再生成至少1个额外的y满足严格大于要求
产生式规则
// 开始符号S(额度0)规则 <S> ::= 'x' <S1> // 开头新增1个x,需1个y补偿,额度变为1 | <S1> 'z' // 结尾新增1个z,需1个y补偿,额度变为1 | <Y0> // 无x/z时,直接生成非空y串 // 通用规则:对任意m≥1,带m个补偿额度的S_m规则 <S_m> ::= 'x' <S_(m+1)> // 新增开头x,补偿额度+1 | <S_(m+1)> 'z' // 新增结尾z,补偿额度+1 | <Y_m> // 停止新增x/z,进入y块生成阶段 // y块生成规则 <Y0> ::= 'y' // 额度为0时,至少生成1个y,满足n>0+0 | 'y' <Y0> // 支持生成任意多连续y <Y_m> ::= 'y' <Y_(m-1)> // 每生成1个y,减少1个待补偿额度(m≥1)
正确性验证
通过典型场景校验文法的匹配结果:
- 最小合法串(a=0,b=0,n=1):对应串
y,由<S> → <Y0> → 'y'生成,满足1>0+0 - 1个x、0个z:需要n>1,最小串为
xyy,生成过程为<S> → 'x' <S1> → 'x' <Y1> → 'x' 'y' <Y0> → 'x' 'y' 'y',满足2>1+0 - 0个x、1个z:需要n>1,最小串为
yyz,生成过程为<S> → <S1> 'z' → <Y1> 'z' → 'y' <Y0> 'z' → 'y' 'y' 'z',满足2>0+1 - 2个x、1个z:a+b=3,需要n>3,最小串为
xxyyyyz,生成过程累计匹配4个y,满足4>2+1
所有生成的串严格遵循x*y*z*的结构,不会出现x/y/z穿插的情况,且y的数量始终比x+z的数量多至少1个,完全符合题目要求。
内容的提问来源于stack exchange,提问作者Daniel James
相关产品推荐
相关产品推荐

