工大編譯原理課件-chapter2語(yǔ)言定義

1、第二章 語(yǔ)言定義School of Computer Science & Technology Harbin Institute of Technology重點(diǎn)：語(yǔ)言的詞法定義、語(yǔ)法定義、語(yǔ)義定義。 難點(diǎn)：語(yǔ)言的語(yǔ)義定義。 2.1 語(yǔ)言概述2.2 基本定義2.3 文法的定義2.4 程序設(shè)計(jì)語(yǔ)言的詞法定義2.5 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法定義2.6 程序設(shè)計(jì)語(yǔ)言的語(yǔ)義定義2.7 機(jī)器語(yǔ)言本章主要內(nèi)容2.1 語(yǔ)言概述什么是語(yǔ)言？2.1 語(yǔ)言概述語(yǔ)言特征自然語(yǔ)言(Natural Language)是人與人的通訊工具語(yǔ)義(semantics):環(huán)境、背景知識(shí)、語(yǔ)氣、二義性難以形式化計(jì)算機(jī)語(yǔ)言(Computer

2、 Language)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語(yǔ)法(Grammar)、語(yǔ)義(semantics) 易于形式化：嚴(yán)格2.1語(yǔ)言概述語(yǔ)言的描述方法現(xiàn)狀自然語(yǔ)言：自然、方便-非形式化數(shù)學(xué)語(yǔ)言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。2.1 語(yǔ)言概述語(yǔ)言形式化的內(nèi)容提取語(yǔ)言(Language)：滿足一定條件的句子集合句子(Sentence)：滿足一定規(guī)則的單詞序列單詞(Token)：滿足一定規(guī)則的字符(Character)串語(yǔ)言是字和組合字的規(guī)則例（自然語(yǔ)言：第譯始二天課今開(kāi)編上節(jié)）今天開(kāi)始上第二節(jié)編譯課2.1 語(yǔ)言概述語(yǔ)言是字及其組合規(guī)則的統(tǒng)一體2.

3、1 語(yǔ)言概述程序設(shè)計(jì)語(yǔ)言形式化的內(nèi)容提取程序設(shè)計(jì)語(yǔ)言(Programming Language)：組成程序的所有語(yǔ)句的集合。程序(Program)：滿足語(yǔ)法規(guī)則的語(yǔ)句序列。語(yǔ)句(Sentence) ：滿足語(yǔ)法規(guī)則的單詞序列。單詞(Token) ：滿足詞法規(guī)則的字符串。例：變量:=表達(dá)式if 條件 then 語(yǔ)句while條件 do 語(yǔ)句call 過(guò)程名(參數(shù)表)2.1 語(yǔ)言概述描述形式文法語(yǔ)法語(yǔ)句語(yǔ)句的組成規(guī)則描述方法：BNF范式、語(yǔ)法(描述)圖詞法單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用語(yǔ)言學(xué)家Chomsky最初從產(chǎn)生語(yǔ)言的角度研究語(yǔ)言。1956年，通過(guò)

4、抽象，他將語(yǔ)言形式地定義為是由一個(gè)字母表中的字母組成的一些串的集合。可以在字母表上按照一定的規(guī)則定義一個(gè)文法（Grammar），該文法所能產(chǎn)生的所有句子組成的集合就是該文法產(chǎn)生的語(yǔ)言?？肆郑↘leene）在1951年到1956年間，從識(shí)別語(yǔ)言的角度研究語(yǔ)言，給出了語(yǔ)言的另一種描述?？肆质窃谘芯可窠?jīng)細(xì)胞中，建立了自動(dòng)機(jī)，他用這種自動(dòng)機(jī)來(lái)識(shí)別語(yǔ)言：對(duì)于按照一定的規(guī)則構(gòu)造的任一個(gè)自動(dòng)機(jī)，該自動(dòng)機(jī)就定義了一個(gè)語(yǔ)言，這個(gè)語(yǔ)言由該自動(dòng)機(jī)所能識(shí)別的所有句子組成。形式語(yǔ)言于自動(dòng)機(jī)理論的產(chǎn)生與作用1959年，Chomsky通過(guò)深入研究，將他本人的研究成果與克林的研究成果結(jié)合了起來(lái)，不僅確定了文法和自動(dòng)機(jī)分別從生

5、成和識(shí)別的角度去表達(dá)語(yǔ)言，而且證明了文法與自動(dòng)機(jī)的等價(jià)性。 20世紀(jì)50年代，人們用巴科斯范式（Backus Nour Form 或 Backus Normal Form，簡(jiǎn)記為BNF）成功地對(duì)高級(jí)語(yǔ)言ALGOL-60進(jìn)行了描述。實(shí)際上，巴科斯范式就是上下文無(wú)關(guān)文法（Context Free Grammar）的一種表示形式。這一成功，使得形式語(yǔ)言在20世紀(jì)60年代得到了大力的發(fā)展。 形式語(yǔ)言與自動(dòng)機(jī)理論的產(chǎn)生與作用形式語(yǔ)言與自動(dòng)機(jī)理論除了在計(jì)算機(jī)科學(xué)領(lǐng)域中的直接應(yīng)用外，更在計(jì)算學(xué)科人才的計(jì)算思維的培養(yǎng)中占有極其重要的地位 計(jì)算思維能力的培養(yǎng)，主要是由基礎(chǔ)理論系列課程實(shí)現(xiàn)的，該系列主要由從數(shù)學(xué)分

6、析開(kāi)始到形式語(yǔ)言結(jié)束的一些數(shù)學(xué)和抽象程度比較高的內(nèi)容的課程組成。它們構(gòu)成的是一個(gè)梯級(jí)訓(xùn)練系統(tǒng)。在此系統(tǒng)中，連續(xù)數(shù)學(xué)、離散數(shù)學(xué)、計(jì)算模型等三部分內(nèi)容要按階段分開(kāi)，三個(gè)階段對(duì)應(yīng)與本學(xué)科的學(xué)生在大學(xué)學(xué)習(xí)期間的思維方式和能力的變化與提高過(guò)程的三個(gè)步驟。計(jì)算思維能力的培養(yǎng)過(guò)程 中學(xué)數(shù)學(xué)數(shù)學(xué)分析 離散數(shù)學(xué)具體.靜止變量.運(yùn)動(dòng)離散.抽象 形式.模型 (基本運(yùn)算系統(tǒng)) (計(jì)算系統(tǒng)) 實(shí) 數(shù) 抽象 集合單一、具體的計(jì)算 一般、形式化的計(jì)算 （實(shí)例計(jì)算） （模型化計(jì)算） 形式語(yǔ)言與自動(dòng)機(jī)理論運(yùn)算范圍特征高水平計(jì)算專(zhuān)業(yè)人才的計(jì)算思維能力的漸進(jìn)培養(yǎng)2.2 基本定義字母表（Alphabet）是一個(gè)非空有窮集合，字母表中

7、的元素稱(chēng)為該字母表的一個(gè)字母（Letter），也叫字符（Character）。例 以下是不同的字母表： a，b，c，d a，b，c，z 0，1 (4) ASCII字母表2.2 基本定義符號(hào)串的定義(1) 是上的一個(gè)符號(hào)串。 其中，是由中0個(gè)字符組成的。(2) 若x是上的符號(hào)串，而a是的元素, 則xa是上的符號(hào)串。(3) y是上的符號(hào)串,當(dāng)且僅當(dāng)它由(1)和(2)導(dǎo)出。由字母表中的符號(hào)所組成的任何有窮序列被稱(chēng)之為該字母表上的符號(hào)串,也稱(chēng)作字。2.2 基本定義設(shè)s是符號(hào)串，則s的前綴：移走s的尾部的零個(gè)或多于零個(gè)符號(hào)后綴：刪去s的頭部的零個(gè)或多于零個(gè)符號(hào)子串: 從s中刪去一個(gè)前綴和一個(gè)后綴子序列:

8、 從s中刪去零或多于零個(gè)符號(hào)(這些符號(hào)不要求連續(xù)）逆轉(zhuǎn)（用SR表示）：將S中的符號(hào)按相反次序?qū)懗龆玫降姆?hào)串長(zhǎng)度：是該符號(hào)串中的符號(hào)的數(shù)目。例如|aab|=3,|=0。2.2 基本定義符號(hào)串的連接和方冪1.連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串。例如，x=ba,y=nana,xy=banana.2.方冪：x0=; x1=x; x2=xx; ； xn=xn-1x; 例如, 設(shè)x=ba, 則 x1= ba, x2=baba, x3=bababa, 2.2 基本定義定義1 設(shè)1、2是兩個(gè)字母表，1與2 的乘積(Product)定義為12=ab|a1，b2 例

9、:1=0,1, 2=a,b, 12 =0a,0b,1a,1b定義2 設(shè)是一個(gè)字母表，的n次冪(Power)遞歸地定義為： 0= n=n-1 n1例： 13 =000,001,010,011,100,101,110,1112.2 基本定義定義3 設(shè)是一個(gè)字母表，的正閉包(Positive Closure)定義為：+=234的克林閉包(Kleene Closure)為：*=0+ =023 2.2 基本定義 例0,1+ = 0，1，00，01，11，000，001，010，011，100， a，b，c，d+ = a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，

10、aad，aba，abb，abc 2.2 基本定義例0,1* = ，0，1，00，01，11，000，001，010，011，100， a，b，c，d* = ，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， 2.2 基本定義定義5 設(shè)是一個(gè)字母表，L *，L稱(chēng)為字母表上的一個(gè)語(yǔ)言（Language），xL，x叫做L的一個(gè)句子。例： 字母表0，1上的語(yǔ)言0，100，110，1，00，110，1，00，11，01，1000，11*01，10*2.3 文法的定義如何實(shí)現(xiàn)語(yǔ)言結(jié)構(gòu)的形式化描述？考慮一個(gè)句子文法要素的提取分析：The

11、 grey wolf will eat the goat謂語(yǔ)主語(yǔ)形容詞名詞動(dòng)詞直接賓語(yǔ)助動(dòng)詞句子動(dòng)原冠詞名詞The grey wolf will eat the goat冠詞句子 主語(yǔ) 謂語(yǔ) （1） 主語(yǔ) 冠詞 形容詞 名詞 （2） 冠詞the 形容詞 grey 謂語(yǔ) 動(dòng)詞 直接賓語(yǔ) （5） 動(dòng)詞 助動(dòng)詞 動(dòng)詞原形 （6） 助動(dòng)詞will 動(dòng)詞原形 eat 直接賓語(yǔ) 冠詞 名詞 （9） 名詞wolf 名詞 goat句子的組成規(guī)則問(wèn)題：如何用符號(hào)來(lái)描述？即如何形式化？終結(jié)符號(hào)集VT = the，grey, wolf,will, eat, goat非終結(jié)符號(hào)集VN = 句子，主語(yǔ)， 謂語(yǔ)，冠詞，

12、形容詞，名詞 ， 動(dòng)詞 ，直接賓語(yǔ) ，助動(dòng)詞 ，動(dòng)詞原形 語(yǔ)法規(guī)則集P = 句子 主語(yǔ) 謂語(yǔ)， 開(kāi)始符號(hào)S = 句子定義句子的規(guī)則的語(yǔ)法組成_終結(jié)符號(hào)集，非終結(jié)符號(hào)集，語(yǔ)法規(guī)則，開(kāi)始符號(hào)問(wèn)題：有了定義句子的規(guī)則，如何判定某一句子是否屬于某語(yǔ)言？ 句子 主語(yǔ) 謂語(yǔ) 冠詞 形容詞 名詞 謂語(yǔ) the 形容詞 名詞 謂語(yǔ) the grey名詞 謂語(yǔ) the grey wolf 謂語(yǔ) the grey wolf 動(dòng)詞 直接賓語(yǔ) . the grey wolf will eat the goat句子的派生（推導(dǎo)）-從產(chǎn)生語(yǔ)言的角度句子的歸約 -從識(shí)別語(yǔ)言的角度-均根據(jù)規(guī)則句子 the grey wolf

13、 will eat the goat the grey wolf will eat the wolf the grey goat will eat the wolf the grey goat will eat the grey符合語(yǔ)法且符合語(yǔ)義的句子僅是： the grey wolf will eat the goat句子的語(yǔ)義要求2.3 文法G 的形式定義文法G為一個(gè)四元組: = (T，N，)T：終結(jié)符(Terminal)集N：非終結(jié)符(Variable)集，TN=語(yǔ)法成分代表某個(gè)語(yǔ)言的各種子結(jié)構(gòu)：開(kāi)始符號(hào)(Start Symbol)，SN代表文法所定義的語(yǔ)言，至少在產(chǎn)生式左側(cè)出現(xiàn)一次2.

14、3 文法G 的形式定義：產(chǎn)生式(Product)集合，被稱(chēng)為產(chǎn)生式（定義式），讀作：定義為。其中(TN)+，且中至少有N中元素的一個(gè)出現(xiàn)。(TN)*。稱(chēng)為產(chǎn)生式的左部(Left Part)，稱(chēng)為產(chǎn)生式的右部(Right Part)。產(chǎn)生式定義各個(gè)語(yǔ)法成分的結(jié)構(gòu)（組成規(guī)則） 2.4 詞法定義幾個(gè)記號(hào)O(X):= empty | X #(X):= any number of X S(X):= X #(; X) List(X):= X #(, X) ASCII The American Standard Code for Information Interchange摘自 2.4 詞法定義addin

15、g_operator:= + | - | or, apostrophe_image:= , array:=array, begin:=begin, caret:=, case:=case, character_string:= string_element #(string_element) , colon:=:, colon_equals:=:=, comma:=, 2.4 詞法定義const:=const, digit:= (1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0), digit_sequence:= digit #(digit), do:=do, do

16、t:=., doubledot:=., downto:=downto, else:=else, end:=end, equals:=, 2.4 詞法定義for:=for, fractional_part:= digit_sequence, function:=function, goto:=goto, identifier:= letter #( letter | digit), if:=if, label:=label, left:=(, left_br:=, letter:= (a | b | c | d | e | f | g | h | i | j | k | l | m | n |

17、o | p | q | r | s | t | u | v | w | x | y | z), multiplying_operator:= * | / | div | mod | and, 2.4 詞法定義nil:=nil, not:=not, of:=of, of:=of, packed:=packed, packed:=packed, procedure:=procedure, program:=program, record:=record, relational_operator:= = | | | = | in, repeat:=repeat, 2.4 詞法定義right:=),

18、right_br:=, scale_factor:= signed_integer, semicolon:=;, file:=file, set:=set, sign:= + | -, signed_integer:= O(sign) unsigned_integer, string_character:= one_of_a_set_of_implementation_defined_characters, string_element:= apostrophe_image | string_character, 2.4 詞法定義then:=then, to:=to, type:=type,

19、unsigned_integer:= digit_sequence, unsigned_real:= unsigned_integer . fractional_part #(e scale_factor |) | unsigned_integer e scale_factor, until:=until, var:=var, var:=var, while:=while, with:=with, 2.5 語(yǔ)法定義-程序program:= program_heading semicolon program_blockprogram hi(out); begin writeln(Hello, W

20、orld!); gram_heading:=program identifier (O( program_parameters) ) |), program merge(infile1, infile2, mergedfile); 2.5 語(yǔ)法定義-塊program_block:= block .begin writeln(Hi); writeln(there!); end .block:= label_declarations constant_definitions type_definitions variable_declarations procedure_functi

21、on_declarations statement_part const n=1; m=2; begin writeln(m+n); endprogram_parameters:= List(identifier), in,out,waveItAllAbout2.5 語(yǔ)法定義-聲明和定義label_declarations:= O(label List(label) semicolon )label:= digit_sequencelabel 1,2,3,911;constant_definitions:= O(const S(constant_definition) semicolon)co

22、nstant_definition:= identifier = constant2.5 語(yǔ)法定義-聲明和定義type_definitions:= O(type type_definition semicolon #(type_definition semicolon) ) type_definition:= identifier = type_denoter variable_declarations:= O(var variable_declaration semicolon #(variable_declaration semicolon) )variable_declaration:=

23、 identifier_list : type_denoterprocedure_function_declarations:= #( procedure_declaration | function_declaration ) semicolon2.5 語(yǔ)法定義-子程序聲明subprogram_declaration:=procedure_declaration | function_declaration2.5 語(yǔ)法定義-過(guò)程聲明procedure_declaration:= procedure_heading semicolon directive | procedure_identif

24、ication semicolon procedure_block | procedure_heading semicolon procedure_blockprocedure_heading:= procedure identifier O(formal_parameter_list)procedure_identification:= procedure procedure_identifierprocedure_block:= blockprocedure_identifier:= identifierdirective:= letter #(letter | digit) type_d

25、enoter:= type_identifier | new_type2.5 語(yǔ)法定義-函數(shù)聲明function_declaration:= function_heading semicolon directive | function_identification semicolon function_block | function_heading semicolon function_blockfunction_heading:= function identifier (formal_parameter_list |) : result_typefunction_block:= blo

26、ck2.5 語(yǔ)法定義-形參和自變量formal_parameter_list:= formal_parameter_section #( semicolon formal_parameter_section)formal_parameter_section:= value_parameter_specification | variable_parameter_specification | procedural_parameter_specification | functional_parameter_specification | conformant_array_parameter_s

27、pecificationvalue_parameter_specification:= identifier_list : type_identifiervariable_parameter_specification:= var identifier_list : type_identifierprocedural_parameter_specification:= procedure_heading2.5 語(yǔ)法定義-形參和自變量functional_parameter_specification:= function_heading conformant_array_parameter_s

28、pecification:= value_conformant_array_specification | variable_conformant_array_specificationvalue_conformant_array_specification:= identifier_list : conformant_array_schema variable_conformant_array_specification:= var identifier_list : conformant_array_schema2.5 語(yǔ)法定義-形參和自變量conformant_array_schema:

29、= packed_conformant_array_schema | unpacked_conformant_array_schemapacked_conformant_array_schema:= packed array O(index_type_specification ) of type_identifierunpacked_conformant_array_schema:= array O(index_type_specification #(semicolon index_type_specification) ) of type_identifier | conformant_

30、array_schemaindex_type_specfication:= identifier . identifier : ordinal_type_identifier2.5 語(yǔ)法定義-常量constant:= signed_number | constant_identifier | character_stringunsigned_constant:= unsigned_number | character_string | constant_identifier | nilunsigned_number:= unsigned_integer | unsigned_realconst

31、ant_identifier:= identifier2.5 語(yǔ)法定義-類(lèi)型type_identifier:= identifiernew_type:= new_ordinal_type | new_structured_type | new_pointer_typeresult_type:= simple_type_identifier | pointer_type_identifiernew_ordinal_type:= enumerated_type | subrange_typenew_structured_type:= O(packed) unpacked_structured_ty

32、penew_pointer_type:= domain_typesimple_type_identifier:= type_identifierpointer_type_identifier:= type_identifierenumerated_type:= identifier_listsubrange_type:= constant . constant2.5 語(yǔ)法定義-類(lèi)型unpacked_structured_type:= array_type | record_type | set_type | file_typedomain_type:= type_identifierarray

33、_type:= array #(index_type #(, index_type) ) of component_typeset_type:= set of base_typefile_type:= file of component_typeindex_type:= ordinal_typecomponent_type:= type_denoterbase_type:= ordinal_typeordinal_type:= new_ordinal_type | ordinal_type_identifierordinal_type_identifier:= type_identifierr

34、ecord_type:= record field_list end2.5 語(yǔ)法定義-類(lèi)型record_section:= identifier_list : type_denoterfield_list:= O( fixed_part #( semicolon variant_part )fixed_part:= record_section #( semicolon record_section)variant_part:= case variant_selector of variant #( semicolon variant)variant_selector:= O( tag_fie

35、ld : ) tag_typevariant:= case_constant_list : field_listtag_field:= identifiertag_type:= ordinal_type_identifiercase_constant_list:= case_constant #( , case_constant) case_constant:= constant 2.5 語(yǔ)法定義-語(yǔ)句procedure_statement:= procedure_identifier O(actual_parameter_list ) | IO_procedure_statement, IO

36、_procedure_statement:= read read_parameter_list | readln readln_parameter_list | write write_parameter_list | writeln writeln_parameter_list, actual_parameter_list:= actual_parameter #( , actual_parameter), 2.5 語(yǔ)法定義-語(yǔ)句optional_file:=O(file_variable ,), read_parameter_list:= optional_file variable_ac

37、cess #( , variable_access), readln_parameter_list:= O( optional_file variable_access #( , variable_access) ), write_parameter_list:= optional_file write_parameter #( , write_parameter), writeln_parameter_list:= O(optional_file write_parameter #( , write_parameter) ), 2.5 語(yǔ)法定義-語(yǔ)句actual_parameter:= ex

38、pression | variable_access | procedure_identifier | function_identifier, file_variable:= variable_access, variable_access:= entire_variable | component_variable | identified_variable | buffer_varible, write_parameter:= expression O( : O(: expression ) ), 2.5 語(yǔ)法定義-語(yǔ)句statement_part:= compound_statemen

39、t, compound_statement:= begin statement_sequence end, statement_sequence:= statement #(semicolon statement), statement:= O( label : ) (simple_statement | structured_statement), simple_statement:= empty_statement | assignment_statement | procedure_statement | goto_statement, 2.5 語(yǔ)法定義-語(yǔ)句structured_sta

40、tement:= compound_statement | conditional_statement | repetitive_statement | with_statement, empty_statement:=, assignment_statement:= variable_access | function_identifier := expression, goto_statement:= goto label, conditional_statement:= if_statement | case_statement, 2.5 語(yǔ)法定義-語(yǔ)句repetitive_statem

41、ent:= repeat_statement | while_statement | for_statementloop:= repeat_statement | while_statement | for_statementwith_statement:= with record_variable_list do statementif_statement:= if boolean_expression then statement O(else_part )case_statement:= case case_index of case_list_element #(semicolon c

42、ase_list_element) O(semicolon |) end2.5 語(yǔ)法定義-語(yǔ)句repeat_statement:= repeat statement_sequence until boolean_expressionwhile_statement:= while boolean_expression do statementfor_statement:= for control_variable := initial_value (to | downto) final_value do statementrecord_variable_list:= record_variabl

43、e #(, record_variable)boolean_expression:= expression2.5 語(yǔ)法定義-語(yǔ)句else_part:= else statementcase_index:= expressioncase_list_element:= case_constant_list : statementcontrol_variable:= entire_variableinitial_value:= expressionfinal_value:= expression2.5 語(yǔ)法定義-表達(dá)式和變量expression:= simple_expression #(relational_operator simple_expression )function_identifier:= identifierentire_variable:= variable_identifiercomponent_variable:= indexed_variable | field_designatoridentified_variable:= pointer_variable buffer