软考编译原理考点-文法

来源:http://www.200818.com/html/xzzq/byyl/3174.html
文法的直观理解
(1)什么是文法:
文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”(或称为“语法” )。
例:有一句子:“我是大学生” 。这是一个在语法、语义上都正确定句子,该句子的结构(称为语法结构)是由它的语法决定的 。在本例中它为“主谓结构”。
如何定义句子的合法性?
如何定义有穷语言、无穷语言?
(2)语法规则:
我们通过建立一组规则(产生式),来描述句子的语法结构。
规定用“::=”表示“由……组成”或“定义为…”。如:
<句子>::=<主语><谓语>
<主语>::=<代词> | <名词>
<代词>::=你 | 我 | 他
<名词>::= 王民 | 大学生 | 工人 | 英语
<谓语>::=<动词><直接宾语>
<动词>::=是 | 学习
<直接宾语>::=<代词> | <名词>
(3)由产生式推导句子:
有了一组产生式之后,可以按照一定的方式用它们去推导或产生句子。
推导方法:从一个要识别的符号开始推导,即用相应产生式的右部来替代产生式的左部,每次仅用一条产生式去进行推导。如:
<句子> Þ <主语><谓语>
<主语><谓语> Þ <代词><谓语>
…………
这种推导一直进行下去,直到所有带< >的符号都由终结符号替代为止。
<句子> Þ <主语><谓语>
Þ < 代词><谓语>
Þ 我<动词><直接宾语>
Þ 我是<直接宾语>
Þ 我是<名词>
Þ 我是大学生

例:有一英语句子:The big elephant ate the peanut.
<句子>::=<主语><谓语>
<主语>::=<冠词><形容词><名词>
<冠词>::=the
<形容词>::=big
<名词>::=elephant
<谓语>::=<动词><宾语>
<动词>::=ate
<宾语>::=<冠词><名词>
<名词>::=peanut
<句子> Þ <主语><谓语>
Þ <冠词><形容词><名词><谓语>
Þ the <形容词><名词><谓语>
Þ the big <名词> <谓语>
Þ the big elephant <谓语>
Þ the big elephant <动词><宾语>
Þ the big elephant ate <宾语>
Þ the big elephant ate <冠词><名词>
Þ the big elephant ate the <名词>
Þ the big elephant ate the peanut
上述推导可写成
<句子> the big elephant ate the peanut
说明:
(1)有若干语法成分同时存在时,我们总是从最左的语法成分进行推导,这称之为最左推导,类似的有最右推导(一般推导)。
(2)从一组产生式可推出不同的句子,如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子,它们 在语法上都正确,但在语义上都不正确。
所谓文法是在形式上对句子结构的定义与描述,而未涉及语义问题。
(4)语法树:
我们用一种树型结构来描述一个句子的语法结构。称之为语法树。如:

百科:http://zh.wikipedia.org/zh/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95#.E5.BD.A2.E5.BC.8F.E5.AE.9A.E4.B9.89

递归全排列算法(java)

/*
* 牛逼全排列算法,标记一下
*/
package string;

public class AllSort{
	public static void main(String[] args) {
		char buf[]={'a','b','c','d','e','g'};
		perm(buf,0,buf.length-1);
	}
	public static void perm(char[] buf,int start,int end){
		if(start==end){//当只要求对数组中一个字母进行全排列时,只要就按该数组输出即可
			for(int i=0;i<=end;i++){
				System.out.print(buf[i]);
			}
			System.out.println();
		}
		else{//多个字母全排列
			for(int i=start;i<=end;i++){
			char temp=buf[start];//交换数组第一个元素与后续的元素
			buf[start]=buf[i];
			buf[i]=temp;

			perm(buf,start+1,end);//后续元素递归全排列

			temp=buf[start];//将交换后的数组还原
			buf[start]=buf[i];
			buf[i]=temp;
			}
		}
	}
}

 

一个好玩的批处理程序

@echo off
rem 夜愿
rem 大家可以修改成自己的喜欢的
rem win7可以读中文 xp好像就只能是英文了
echo            《无题》
echo.
echo                  李商隐
echo.
echo 相见时难别亦难,东风无力百花残。
echo 春蚕到死丝方尽,蜡炬成灰泪始干。
echo 晓镜但愁云鬓改,夜吟应觉月光寒。
echo 蓬山此去多无路,青鸟殷勤为探看。
mshta vbscript:createobject(“sapi.spvoice”).speak(“无题”)(window.close)
mshta vbscript:createobject(“sapi.spvoice”).speak(“李商隐”)(window.close)
mshta vbscript:createobject(“sapi.spvoice”).speak(“相见时难别亦难,东风无力百花残,春蚕到死丝方尽,蜡炬成灰泪始干。晓镜但愁云鬓改,夜吟应觉月光寒,蓬山此去多无路,青鸟殷勤为探看。”)(window.close)