5 非上下文无关语言

有些少量不能仅用文法描述的语法构造。

先声明，后使用的语法构造

用形如 $wcw$ 的串来抽象表示，第一个 $w$ 表示标识符 $w$ 的声明，$c$ 表示中间的程序片段，第二个 $w$ 表示对这个标识符的使用。

$L_1=\{wcw|w\in(a|b)^*\}$，这个语言不是上下文无关的。

参数个数检查的问题

用形如 $a^nb^mc^nd^m$ 的串组成，这里 $a^n,b^m$ 表示两个分别有 $n$ 和 $m$ 个参数的函数声明形式参数列表，$c^n,d^m$ 表示实际参数。这个语言检查实参个数和形参个数是否相等。

$L_2=\{a^nb^mc^nd^m|n\ge1,m\ge 1\}$，这个语言不是上下文无关的。

检查一次调用中的参数个数是否正确通常是在语义分析的时候完成的。

本文阅读量