Microsoft PowerPoint L03-Syntex and Semantics-1-students ( )

Transcription

1 プログラミング言語論 A (Concepts on Programming Languages) 趙建軍 (Jianjun Zhao) of Programming Languages.html 1 第 3 回 構文と意味 (1) (Syntax and Semantics)

2 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 3 言語の形式的な定義の必要性 プログラミング言語の定義 構文 : 文字列によるプログラムの構成法 意味 : その文字列の表わす計算 形式的な定義の必要性 プログラミング言語でプログラムを書く プログラミング言語の処理系の作成 言語の機能 プログラムの性質の考察 4 2

3 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 5 How to Describe a Language? Layered structure of language definition The alphabetbasic Lexical structure Syntactic structure Semantics symbols words statements meaning 6 3

4 例 十進数字の数の位取り表記法 語言語意味 並べる 文 表わす ( 数字 ) 数の位取り表記 ( 自然数 ) 数の位取り表記法と自然数との関係 7 形式言語論の文法の考え方 語 ( アルファベット, alphabet) 有限個の記号の集合 Digit ::= 言語 (language) 語から選んだ記号を並べた記号列で 特定の性質をもつものの集合 Numeral ::= Digit Numeral Digit 8 4

5 文法 : 代数型による表現 語 Digit ::= data Digit = Digit_0 Digit_1 Digit_2 Digit_3 Digit_4 Digit_5 Digit_6 Digit_7 Digit_8 Digit_9 言語 (language) Numeral ::= Digit Numeral Digit data Numeral = Single Digit Composite Numeral Digit 9 意味の記述 構成法に基づく場合分けによる関数定義 Numeral の場合 : 数字列 x(n-1)... x1 x0 に数 x(n-1) 10^(n-1)+... x1 10+x0 を対応づける numval :: Numeral -> Int numval (Single d) = digval d numval (Composite n d) = numval n * 10 + digval d digval :: Digit -> Int digval Digit_0 = 0 digval Digit_1 =

6 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 11 アルファベット 語 アルファベット ( ) もっとも基本的かつ原子的な記号の有限集合 自然言語 : ひらがな 漢字 プログラミング言語 : JIS, ISOなどで定義されたキャラクタセット ( マイクロ ) キーワット 識別子 演算子記号 区切り記号 ( マクロ ) アルファベット上の語 ( または文 ) に属する記号の有限長の系列 特に 長さが 0 の語は空語 12 6

7 アルファベット 語 任意の記号 ( または記号列 ) の集合を S とする 1 S S S の記号 2つからなる記号列の集合を S² と表す 2 S { ab a S, b S} 0 特に S { } S i { wa w S i 1, a S}( i 1) S i ( i 0) すべての和集合をSの閉包 (closure) といい S* で表す アルファベット 語 S* - {ε} を S と表すこともある S* = Sº U S¹ U S² U... S = S¹ U S² U... 例 :S={a,b} とすると Sº = {ε} S¹ = {a, b} S² = {aa, ab, ba, bb}, S³ = {aaa, aab, aba, abb, baa, bab, bba, bbb} S* = {ε, a, b, aa, bb, ba, bb, aaa,...} 7

8 言語 形式言語とは 上の語の集合 言語は有限集合の場合もあるが 一般には無限集合 二進数の例 : = {0, 1}, {0, 1} 無限集合となりうる形式言語を有限の長さの記述で表現する三つの方法がある 正規表現 (Regular Expression) 形式文法 (Formal Grammar) オートマトン (Automaton) + 15 言語 形式言語とは 上の語の集合 言語は有限集合の場合もあるが 一般には無限集合 二進数の例 : = {0, 1}, {0, 1} 無限集合となりうる形式言語を有限の長さの記述で表現する三つの方法がある 正規表現 (Regular Expression) 形式文法 (Formal Grammar) オートマトン (Automaton)

9 正規表現 (regular experession) 言語を表す一つの表現法 正規表現の考え方はいろいろな場所で用いられている データベースの検索 パーソナルコンピュータやワークステーションのシェル a* : a で始まる名前を持つファイル ( の集合 ) を指定したことになる 17 正規表現 (regular expression) 正規表現は 次の規則によって 再帰的に定義される 1. ε, φは 正規表現である ただし 2. a は 正規表現である ただし a F, G を正規表現とするとき 3. (FG) は正規表現である 4. (F G) は正規表現である 5. (F*) は正規表現である 6. (F) は正規表現である 18 9

10 正規表現 (regular expression) 正規表現とは ある種の制約条件に従う文字列として定義されている, 例えば ={a, b} 規則 (1),(2) から ε, φ, a, b は正規表現 規則 (3),(4),(5),(6) から (ab), (aa), (a b), (a*), (b*), (a) (ab)a, b(aa), ((a*) b) は正規表現 19 正規言語 (regular language) 正規表現の表す言語正規表現 R が表す言語 L(R) を次のように再帰的に定義する 1. L(ε) = {ε}, L(φ) = { } ただし, 2. L(a) = {a} ただし, a F, G を正規表現とするとき 3. L(FG) = {σ1σ2 σ1=l(f), σ2=l(g) } [ 連接 ] 4. L(F G) = L(F) U L(G) [ 集合和 ] 5. L(F*) = (L(F))* [ 閉包 ] 6. L((F)) = L(F) 20 10

11 例 正規表現 a((ab)*) が表す言語 L(a((ab)*)) は 次のような集合である {a, aab, aabab, aababab,...} a で始まり その後に ab の繰り返しが続くような語の集合 21 例 Let = {0, 1} 1 { 1 } 0 1 {01} 0 1 {0, 1} 0(0 1) {00, 01} 0(0 1)(1 ) {001, 011, 00, 01} 0(01)* {0, 001, 00101, , } 22 11

12 有限オートマトン 正規表現を言語認識ルーチンに変換するよい方法は 正規表現から一般化した遷移図を作ることである この遷移図を ( 非決定性 ) 有限オートマトン ( (Nondeterministic) Finite Automaton; NFA) と呼ぶ 開始 a a b b b 最終状態 (a b)*abb を認識する NFA 23 Quiz Time! 24 12

13 Match and Create Regular Expressions 1. 0(0 1)*0 2. ((ε 0)1*)* 3. ((0 1)0(0 1))* a b c d e 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 26 13

14 アルファベット 語 言語 アルファベット ( ) もっとも基本的かつ原子的な記号の有限集合 自然言語 : ひらがな 漢字 プログラミング言語 : JIS, ISO などで定義されたキャラクタセット ( マイクロ ) キーワット 識別子 演算子記号 区切り記号 ( マクロ ) アルファベット上の語または文 に属する記号の有限長の系列 特に 長さが 0 の語は空語 27 アルファベット 語 言語 形式言語とは 上の語の集合 言語は有限集合の場合もあるが 一般には無限集合 二進数の例 : = {0, 1}, {0, 1}+ 無限集合となりうる形式言語を有限の長さの 記述で表現する三つの方法 正規表現 形式文法 オートマトン 28 14

15 文脈自由文法 (Context-free grammar) 言語に属する文は構造を持っている if 文 : if a > b then m:= a else m:=b キーワード : 条件式 : 代入文 : if, then, else a>b m:=a, m:=b このような条件式 代入文などの構造を句 (phase) と呼ぶ 29 文脈自由文法 (Context-free grammar) 文脈自由文法 G は 以下のような字句の構造を規定する形式文法の一つで 4 字組 (T, N, S, P) で表れる : T: 終端記号からなる有限集合 N: 非終端記号からなる有限集合 S: 開始記号 ( 非終端記号の一つ S N ) P: 生成規則からなる有限集合 N x (N T)* X Nとする X e 或は X Y 1 Y 2... Y n where Y i N T 30 15

16 文脈自由言語 (Context-free grammar) 文脈自由文法 G が生成する言語 L(G) は 以下のように定義する L( G ) { w S w, w T *} * 文脈自由文法 G が生成する言語 L(G) は 開始記号 S から導出を繰り返して得られる文の集合である このような言語 L(G) を文脈自由言語 (context free language) と呼ぶ * S w( w ( T * N ) ) 31 文脈自由文法の例 A fragment of MiniJava STATE if ( EXPR ) STATE STATE LVAL = EXPR EXPR id The principle of Compiler 16

17 文脈自由文法の例 A fragment of MiniJava STATE if ( EXPR ) STATE LVAL = EXPR EXPR id Shorthand notation with The principle of Compiler 文脈自由文法の例 A fragment of MiniJava STATE if ( EXPR ) STATE LVAL = EXPR EXPR id Shorthand notation with The principle of Compiler 17

18 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 (S S0) 35 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 S10 (S S1) 36 18

19 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 S10 S010 (S S0) 37 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 S10 S010 S0010 (S S0) 38 19

20 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 S10 S010 S (S 1) 39 例題 1 次の文法 G1 は 0,1 からなる長さ 1 以上の任意の系列からなる言語を生成する G1 = (N,T,S,P), N={S}, T={0,1} P = {S 0, S 1, S S0, S S1} 文 は次のように生成される S S0 S10 S010 S

21 例題 2 次の文法 G2 は 先頭に無駄な 0 のない二進表現からなる言語を生成する G2 = (N,T,S,P), N={S,A}, T={0,1} P = { S 0 A, A 1 A0 A1 } 文 は次のように生成される S A A0 A10 A010 A 例題 3 次の文法 G3 は 対応のとれた括弧の列からなる言語である G3= (N,T,S,P), N={S}, T={(,)} P = { S ( ) (S) SS } 文 (( ) ( )) ( ) は次のように生成される??? 42 21

22 例題 3 次の文法 G3 は 対応のとれた括弧の列からなる言語である G3= (N,T,S,P), N={S}, T={(,)} P = { S ( ) (S) SS } 文 (( ) ( )) ( ) は次のように生成される S SS (S)S (SS)S (SS)( ) (( )S)( ) (( )( ))( ) 43 解析木 各非終端記号からどのような記号列が導出されたかを木の形で表現できる このような木を解析木あるいは構文木 (parse tree) 内部頂点 : 非終端記号 葉 : 終端記号 ラベルとして付けられる 葉のラベルを左から順に並べた記号列は 導出された文となっている 文法 G と G によって生成される文 s が与えられたとき s の解析木もしくは同等の情報を求めることを構文解析 (syntax analysis, parsing) するという 自動解析ツール :yacc, lex (Unix) 44 22

23 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 45 BNF 記法 (1) Backus Normal Form (Backus Naur Form) 46 23

24 John Backus ( ) Fortran Programming language Fortran Compiler (1957) Took 18 staff years to implement Turing Award 47 BNF 記法 (1) Backus Normal Form (Backus Naur Form) 48 24

25 Peter Naur(1928-) 2005 Turing Award For fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming. 49 BNF 記法 (2) 文脈自由文法を簡潔に表現する記法 左辺が同じ非終端記号の規則を 縦棒 を使って まとめて表す ( 例 ) 文脈自由文法 G = (T, N, S, P) N = { S } T = { (, ) } P = { S ( ), S (S), S SS } は BNF 記法では <paren> ::= ( ) (<paren>) <paren><paren> と表せる 50 25

26 BNF 記法 (3) 基本記号 基本記号 ( トークン, token): 表記に用いる基本的要素 語彙 ( アルファベット, alphabet): 基本記号の有限集合 構文単位 構文単位 (syntactic unit): 構文上のひとまとまりの構成 構文単位名 のように書く 51 BNF 記法 (4) 構文規則 構文単位名 ::= 構成 1 構成 2... 構成 n 構成 i 基本記号や 構文単位名 をいくつか並べたもの 空の列 : ε Numeral ::= Digit Numeral Digit 52 26

27 BNF 記法 (5) 加減演算式を定める構文規則 基本記号 {0,1, 2, 3, 4, 5, 6, 7, 8, 9, +, -} 構文規則 Expr ::= Numeral Expr + Expr Expr - Expr> Numeral ::= Digit Numeral Digit Digit ::= 曖昧の文法に注意 53 代数型による構文の表現 構文単位名 ::= 構成 1 構成 2... 構成 n data 代数型名 = 構成子 1 構成要素列 1 構成子 2 構成要素列 2... 構成子 n 構成要素列 n 54 27

28 代数型による構文の表現 ( 続 ) Expr> ::= data Expr = Num Numeral Pexpr Expr Expr Mexpr Expr Expr data Numeral = Single Digit Composite Numeral Digit data Digit = Digit_0 Digit_1 55 構文解析 記号列が構文規則で定まる言語の文であることを解析する 例 : の構文 Pexpr (Num (Composite ( Composite (Simple Digit_2) Digit_9 ) Digit_1 ) ) (Num (Composite (Simple Digit_3) Digit_1 ) ) 56 28

29 ( 抽象 ) 構文木 文の構成を構成子を用いて表現したもの 構成子 : 節 構成要素 : 枝 57 講義内容 構文と意味 構文の記述 正規表現 文脈自由文法 BNF 構文図式 抽象構文 意味の記述 58 29

30 構文図式 BNFと記述力は変わらない 直感的でわかりやすい [ プログラム ] ; 変数宣言 関数定義 [ 変数宣言 ] 要素型 識別子 [ 関数定義 ] 返戻型 識別子 ( 変数宣言 ) ブロック, 59 構文図式 [ プログラム ] ; 変数宣言 関数定義 60 30

31 構文図式 [ ブロック ] { 文 } 61 [ 文 ] 変数宣言 識別子 = 式 ; 関数呼出し ; if ( 条件式 ) 文 while ( 条件式 ) 文 ブロック return 式 ; 62 31

32 63 [ 関数呼出し ] 識別子 ( 式 ), [ 式 ] 項 項 加減演算子 [ 項 ] 因数 因数 乗除演算子 64 32

33 [ 条件式 ] 式 ==!= > >= < <= 式 65 [ 加減演算子 ] + [ 乗除演算子 ] * - / [ 返戻型 ] 要素型 void [ 数字 ] と [ 英字 ] は非終端記号なので 本来はそれらも終端記号に至るまでの定義が必要 しかし 省略されている 前回の BNF の例でも省略されている [ 識別子 ] 英字 英字 数字 [ 整数 ] 数字 [ 要素型 ] int 66 33