编译原理笔记

编译消除左递归 

A->Aα|β

结果

A->βR

R->αR|ε

串的各部分术语  

一个串abcde……1234一共有n个
这个串的前缀，从这个串的尾部开始删除连续的0个、1个……n个 ，
例如abcde……1234，abcde……123，abcde……12，ε
串的前缀有n+1个；

这个串的后缀，从这个串的开始处删除连续的0个、1个……n个，
例如abcde……1234，bcde……1234，cde……1234，ε
串的后缀有n+1个

这个串的子串，删除某个前缀并删除某个后缀得到的串
例如 abcde……1234，bcde……123，abcde……12，ε
串的字串有C(n,0)+C(n,1)+C(n,2)=1 + n + n*(n-1)/2 = 1+(n+1)*n/2个

这个串的真前缀n-1真后缀n-1真子串n + n*(n-1)/2-1 = n*(n+1)/2-1个
【真去除 ε和和这个串自身】

这个串的子序列，从这个串中随意剔除0个、1个、……n个
例如 abcde……1234， ae……1234， ade……14，ε
串的子序列有2^n

FIRST集和FOLLOW集  

省略号代表其他相关产生式得出的终结符号,一开始的时候，省略号里面是没有的

求FIRST集
情况壹  如果A只在→的右边出现，那么FIRST(A)={A},例子M→α,FIRST(α)={α}
情况貳  对于A→BCDEFG，
               一 如果无B→ε,那么FIRST(A)={……}∪FIRST(B),接着求FIRST(B)
               二 如果有B→ε,那么FIRST(A)={……}∪(FIRST(B)-{ε})∪FIRST(CDEFG),接着分别求FIRST(B)-{ε}、FIRST(CDEFG)
情况叁 如果G→ε，那么FIRST(G)={……}∪{ε}

求FOLLOW集
情况壹 如果S是开始符号(一般是第一个产生式)，那么FOLLOW(S)={……,$} 
情况贰 一 如果有产生式A→αBCD，且ε不属于FIRST(CD)那么FOLLOW(B)={……}∪(FIRST(CD))
             二 如果有产生式A→γBCD，且ε属于FIRST(CD)那么FOLLOW(B)={……}∪(FIRST(CD)-{ε})∪FOLLOW(A)
情况叁  如果有产生式M→CDB，那么FOLLOW(B)={……}∪FOLLOW(M) 


例子
对于文法G[A]
A→BCc|gDB
B→bCDE|ε
C→DaB|ca
D→dD|ε
E→gAf|c

FIRST集先看→左边
FIRST(A)=FIRST(BCc)∪FISRT(gDB)
               =(FIRST(B)-{ε})∪FIRST(Cc)∪{g}
              ={b}∪FIRST(DaBc)∪FIRST(cac)∪{g} 
              ={b}∪FIRST(dDaBc)∪FIRST(aBc)∪{c}∪{g}
              ={b,d,a,c,g}
FIRST(B)=FIRST(bCDE)∪FIRST(ε)
              ={b,ε}
FIRST(C)=FIRST(DaB)∪FIRST(ca)
               =FIRST(dDaB)∪FIRST(aB)∪{c}     相当于(FIRST(D)-{ε})∪FIRST(aB)∪{c}
              ={d,a,c}
FIRST(D)=FIRST(dD)∪FIRST(ε)
               ={d,ε}
FIRST(E)=FIRST(gAf)∪FIRST(c)={g,c}
-------------------------------------------------------------------------------------------------------
FOLLOW集先看→右边
FOLLOW(A)={$}∪{f}={f,$}
FOLLOW(B)=FIRST(Cc)∪FOLLOW(A)∪FOLLOW(C)
                      ={d,a,c}∪{f,$}∪FOLLOW(C)先去求FOLLOW(C)再来补
                      ={a,c,d,g,f,$}
FOLLOW(C)={c}∪FIRST(DE)
                      ={c}∪{d}∪FIRST(E)
                     ={c,d,g}
FOLLOW(D)=(FIRST(B)-{ε})∪FOLLOW(A)∪FIRST(E)∪{a}∪FOLLOW(D)
                     ={b}∪{f,$}∪{g,c}∪{a}
                     ={a,b,g,c,f,$}
FOLLOW(E)=FOLLOW(B)={a,c,d,g,f,$}

C语言声明转类型表达式  

typedef struct              //结构体

{
int a,b;
}CELL,*PCELL;
CELL foo[100];
PCELL bar(int x,CELL y);                //函数声明
/*
写出foo和bar的类型表达式
CELL      record((a  x  integer)x(b  x  integer))
PCELL   pointer(CELL)
foo        array(100,CELL)
bar        integer  x CELL  →  PCELL
*/

三地址指令  

双目运算
 x=y操作符z         例子：x=a+2 
---------------------------------------------------------------------
单目元算
x=操作符y            例子：x=-1
-------------------------------------------------------------------
复制指令
x=y                         
----------------------------------------------------------------
带下标的复制指令
a[t]=y       
x=y[t]
例子:语句a[i]=b[j]+*p的三地址码
t1=i*4       //注释这里是int类型乘4，float类型乘8
t2=j*4        //注释这里是int类型乘4，float类型乘8
t3=b[t2]
t4=*p
t5=t3+t4
a[t1]=t5
--------------------------------------------------------------------
无条件转移
goto  L

条件转移指令
if x goto L                     // x为真转移    
if False x goto  L         // x为假转移
if x 关系符 y goto  L   //满足关系转移，否则接之后的指令
------------------------------------------------------------------------------------
函数/过程调用
param  x  //传递参数
call  function,n//过程调用，n代表参数个数
y=call function,n// 函数调用   ，n代表参数个数      
例子：语句y=fun(x+1) 的三地址码
t1=x+1
param  t1
y=call  fun,1 
--------------------------------------------------------------------------------------
地址及指针赋值
x=&y
x=*y
*x=y
例子:语句a[i]=b[j]+*p的三地址码
t1=i*4
t2=j*4
t3=b[t2]
t4=*p
t5=t3+t4
a[t1]=t5