2024年10月6日星期日2024年10月6日星期日程序设计语言是一种形式语言，与自然语言既有相似的性质又有本质的不同。最主要的区别是：形式语言的规则简单、严格、无例外、无二义性。编译程序的正确转换建立在对程序设计语言的精确定义和描述基础上。语法——文法是描述语言语法的形式规则语义——语言中各语句的含义语用——从使用者的角度对语言的描述2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日文法的直观概念：以汉语中的“我是大学生”为例。文法的形式定义：P10的定义1.1例2-1，文法G=（，，P，S）是描述标识符的文法，则其中：={标识符，字母，数字}={a,b,c….x,y,z,0,1,2,3…9}P={<标识符><字母>|<标识符><字母>|<标识符><数字><字母>a|b|c|….|z<数字>0|1|2|….|9}S=<标识符>2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日例2-3，利用例2-2中的文法，推导出文法的句子012：最左推导：N=>S=>SD=>SDD=>DDD=>0DD=>01D=>012最右推导：N=>S=>SD=>S2=>SD2=>S12=>D12=>012在这里，NS为长度为1的推导，NSD为长度为2的推导N012为长度为7的推导。其中，对于NS来说，S是N的直接推导，或N是S的直接归约。一些规定：=>推导=>规范推导长度大于零的推导长度可为零的推导长度为n的推导课堂作业：设有文法G[S]：S→a|ε|（T）T→T，S|S请给出句子（a,(a,a))的最左、最右推导。2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日2024年10月6日星期日定义：设G[<S>]是一个文法，并设w=xuy是该文法的一个句型。若<S>*x<U>y且<U>+u，则称u为句型w=xuy对非终结符<U>的一个短语。若<S>*x<U>y且<U>u，则称u为句型w=xuy相对于非终结符<U>的一个简单(直接）短语。任何一个句型的最左简单短语称为柄短语（句柄）。含有终结符的短语，并且不存在也具有这种性质真子串的短语称为素短语。P72例：表达式文法G[<E>]：<E>→<E>+<T>|<T><T>→<T>*<F>|<F><F>→(<E>)|i对句型i*(<E>)的推导为：<E><T><T>*<F><F>*<F>i*<F>i*(<E>)对应的推导树为：使用推导树计算句型（句子）的短语简单、明了推导<S>*x<U>y<U>+u等价于：等价于：<S><U>x<U>yu因此称u是句型xuy(对<U>)的一个短语等价于：<S>x<U>yu若子树高度为1，则u还是直接短语，最左直接短语为句柄。若u是含有终结符的最小的短语，则为素短语，句型最左边的素短语称为最左素短语（P72）。例：上例的文法G[<E>]和句型i*(<E>)容易从推导树中看出：短语：i,i*(<E>),(<E>)直接短语：i，(<E>)句柄（左直接短语）：i素短语：i，(<E>)最左素短语：i例，找出针对左边文法的句型T+T*F+a的所有短语、简单短语(直接短语)、素短语和句柄。此句型对应的分析树为：