运算符优先文法的 LEADING 和 TRAILING 操作是什么?
领导
如果产生式的形式是A→aα或A→Baα,其中B是非终结符,并且α可以是任何字符串,那么RHS上的第一个终结符是
Leading(A)={一}
如果生产的形式是A→Bα,如果a在LEADING(B)中,那么a也将在LEADING(A)中。
尾随
如果产生式的形式为A→αa或A→αaB,其中B是非终结符,并且α可以是任何字符串,那么,
尾随(A)={a}
如果生产形式为A→αB。如果a在TRAILING(B)中,则a将在TRAILING(A)中。
计算LEADING的算法
输入-上下文无关语法G
输出−LEADING(A)={a}iff布尔数组L[A,a]=true
Method-ProcedureInstall(A,a)将使L(A,a)为真,如果之前不是真的。
开始
对于每个非终端A和终端a
L[A,a]=false;
对于形式A⟶aα或A→Baα的每个产生式
安装(A,a);
虽然堆栈不为空
弹出顶对(B,a)形成Stack;
对于形式A→B的每个产生式α
安装(A,a);
结尾
程序安装(A,a)
开始
如果不是L[A,a]那么
L[A,a]=真
将(A,a)压入堆栈。
结尾
计算TRAILING的算法
输入-上下文无关语法G
输出−TRAILING(A)={a}iff布尔数组T[A,a]=true
方法
开始
对于每个非终端A和终端a
T[A,a]=false;
对于形式A⟶αa或A→αaB的每个产生式
安装(A,a);
虽然堆栈不为空
弹出顶对(B,a)形成Stack;
对于形式A→αB的每个产生式
安装(A,a);
结尾
程序安装(A,a)
开始
如果不是T[A,a]那么
T[A,a]=真
将(A,a)压入堆栈。
结尾
计算运算符优先关系的算法
输入-运算符语法
输出-终端和符号之间的优先关系。
方法
开始
对于每个产生式A→B1,B2,………。乙ñ
对于i=1到n–1
如果Bi和Bi+1都是终端,那么
设置Bi=Bi+1
如果i≤n−2且Bi和Bi+2都是终结符,而Bi+1是非终结符,则
设置Bi=Bi+1
如果Bi是终结符&Bi+1是非终结符,那么对于LEADING(Bi+1)中的所有a
设置Bi<。一种
如果Bi是非终结符&Bi+1是终结符,那么对于TRAILING(Bi)中的所有a
设置一个.>Bi+1
结尾