スライド 1

Size: px

Start display at page:

Download "スライド 1"

さあしゃくだら
5 years ago
Views:

1 プログラミング言語処理系論 (3) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース )

2 仕様とは? 規格とは? 仕様 (Specification): ( 言語が ) みたすべき要求事項の集合規格 (Standard): ( 複数の仕様の ) 相互運用のために市場である権威のもとに調整された仕様この講義で本来問題になるのは仕様ただし規格が問題になるのは言うまでもない

3 前回の講義で述べたこと ( 現象面からの観察として ) プログラミング言語処理系の実装が複数出てくると規格の必要性が議論されるようになります規格を作るモチベーションとしてはいろいろなものがあります ( 善意から邪悪まで ) プログラミング言語は仕様規格が問題になる重要な分野です

4 実は仕様規格が重要な意味を持つもう一つの分野としてネットワークがありますプロトコル ( 通信規格 ) 相互運用性が常に問題になってきました L1 から L7 まで常に ISO や ITU など伝統的な規格作成の場の他に IETF が大きな役割をもっています RFC

5 プログラミング言語の仕様を読めるようにするわけですがどのような書き方に従っているのか特定の意味を持つ語がどのくらい使われているのか等々を実感するのに最初から大部な規格書を読むのは少し荷が重いというわけでネットワークに関係する文書から簡単なものを少し引っ張ってきます

6 今までプログラミング言語で講義した来たことを HTTP+HTML でやってみますブラウザが HTML を正しく理解できない時点でアウトブラウザと Web サーバが HTTP を正しく理解できない時点でアウトアウト = 処理が正しく行われない

7 HTML の仕様と言って思うものは何? 利用者 ( プログラマ ) ブラウザ ( 処理系 ) HTML 文書 ( プログラム ) サーバ

8 正しい HTML 文書とは? ブラウザが正しく表示できればそれは正しい HTML 文書か? どのブラウザで表示できれば正しい HTML 文書か? IE, FireFox, Safari, Opera, あるブラウザだけで正しく表示されなくない HTML 文書があったとき悪いのは HTML 文書かブラウザか?

9 Web の市場の大きさ Web ブラウザの HTML 文書の仕様の解釈が大きな力を持つビジネスの力共通の理解がないと次のようなことが平気でおきる便利な機能を相手に黙って実装この仕様を持つ HTML 文書はこのブラウザで表示可能とうたう HTML 仕様の世界の支配

10 規格 HTML の規格の歴史 HTML 1.0 以前 HTML 1.0 IETF より 1993 年 HTML 2.0 IETF RFC 年 HTML 3.2 W3C 1997 年 HTML 4.01 W3C 1999 年 HTML 5

11 ブラウザベンダーの規格対応 IE 5 HTML 4.01 対応 IE5 は HTML 独自拡張部分が多く開発者を悩ませた ( らしい ) Netscape Navigator 4 はレンダリングの点で IE との不整合が存在した現在は規格への整合性を求める声が強く行儀の悪い仕様は少なくなっている開発者を含む市場の声はやはり大きい

12 HTML の規格現在の規格 HTML これを読む? 規格は DTD で記述されているプログラミング言語の標準的な定義の仕方ではないので興味のある人は自分で読んでください

13 利用者の立場でなく開発者の立場に立ってみる何を作ったらよいのか決められていないのは困るとにかく決めてくれ何かを決めている文書が解釈に幅がある文書だと困る私の解釈が正しいことを誰か保証してくれ自然言語で書く場合解釈の曖昧さは宿命的

14 ということで今回の予定規格を読む訓練をしましょうテキストは XML の定義文書 Extensible Markup Language (XML) 1_1 (Second Edition) BNF の読み方を理解しましょう定義の仕方規格独特の言い回しを理解しましょう解釈の曖昧さを排除するやり方

15 次回 ( たぶん次々回 ) の予定文法からパーサを作る BNFをそのまま解釈する出力としていろいろなものを考えるインタープリタで実行解析木を解釈機械語に翻訳して実行 BISON,YACC の基礎知識は不要です

16 What is XML? やみくもに規格を読んでもわかりませんで XML ってなに?

17 <?xml version="1.0"?>  - <addressbook> - <personal number="0001"> <name>a さん </name> <address> 神奈川県 </address> <tel> </tel> < addr="xxx@xxx.xx.xx" /> </personal> - <personal number="0002"> <name>b さん </name> <address> 東京都 </address> <tel> </tel> < /> </personal> </addressbook>

18 What is XML for? Web 間 /Web とブラウザ間を流れるデータの共通フォーマットとして設計インターネット上のデータ流通に特化マークアップ言語として定義 extensible Markup Language Web だから文書の形式 HTML SGML

19 蛇足実質的にはタグ <address> </address>, <h1> </h1> などマークアップ文書に関するメタな情報の指定 ( もともとは編集用語 ) 段落指定フォントサイズ指定などを行なう指定するものをタグという

20 具体例をいくつか <?xml version="1.0"?>  <!DOCTYPE addressbook SYSTEM "addressbook.dtd"> <addressbook> <personal number="0001"> <name>a さん </name> <address> 神奈川県 </address> <tel> </tel> < </personal> <personal number="0002"> <name>b さん </name> <address> 東京都 </address> <tel> </tel> < /> </personal> </addressbook> <!ELEMENT addressbook (personal*)> <!ELEMENT personal (name,address,tel, )> <!ATTLIST personal number CDATA #REQUIRED> <!ELEMENT name (#PCDATA)> <!ELEMENT address (#PCDATA)> <!ELEMENT tel (#PCDATA)> <!ELEMENT EMPTY> <!ATTLIST addr CDATA #IMPLIED>

21 XML の構造 <tag> ではじまり </tag> でおわる HTML は違うけど XML では許されないか? <tag/> ってなに? これで大体はわかるけど <tag a= abc > と中に何かを書くことができる大体でいいの? abc は引用符で囲まなければならないのか? HTMLでは違うぞタグはネストしてよい

22 XML の構造言語を定義するときの標準的な手法を説明する何を定義すると言語が定義されるのか? 言語の構造 (Syntax を含む ) 言語の解釈 (Semantics) どのように定義すると定義になるのか? BNF 定義の手法に標準的な方法はあるか? 言い回し

23 XML の仕様書規格はここ / まずは目次を見てみる 1 Introduction 2 Documents 3 Logical Structures 4 Physical Structures 5 Conformance 6 Notation

24 ここからわかること XML は Document を定めている XML には Logical Structure と Physical Structure がある Notation があるということはわからない表記があったらこの章を見ればよいということだな

25 通常のプログラミング言語では Fortran Overview 2. Fortran Concepts 3. Lexical tokens, and source form 4. Types 5. Attribute declarations and specifications 6. Use of data objects 7. Expressions and assignment 8. Execution control 9. Input/output statements 10. Input/output editing

26 続き 11. Program units 12. Procedures 13. Intrinsic procedures and modules 14. Exceptions and IEEE arithmetic 15. Interoperability with C. 16. Scope, association, and definition

27 大体のあたりをつけられるか? 慣れればOK 例えば logical structureとphysical structureは Documentsで説明されている Physically, the document is composed of units called entities. An entity may refer to other entities to cause their inclusion in the document. A document begins in a "root" or document entity. Logically, the document is composed of declarations, elements, comments, character references, and processing instructions, all of which are indicated in the document by explicit markup.

28 Notation? Notation をざっと見るとどのような記述技術が使われているかわかる The formal grammar of XML is given in this specification using a simple Extended Backus-Naur Form (EBNF) notation. Each rule in the grammar defines one symbol, in the form symbol ::= expression

29 XML の構造形式文法の理論を用いる (Chomsky et.al.) 言語を生成する規則の集合 ( 文法 ) を与える S1 S2 S3 Sn T1 T2 Tm 左辺にマッチした記号列を規則を用いて右辺に変換する記号にはこれ以上の変換ができない終端記号とそうでない非終端記号がある有限回の変換で終端記号の列を生成する生成される列の集合を言語という

30 簡単な例を言語と文法の例 S P P a P a P b P b P 言語の生成の例 S -> P -> a P a -> ab P ba -> aba P aba -> abaaba

31 言語のクラス Regular Expression 左辺 = 1, 右辺は terminal+non-terminal のみ Context Free Grammar 左辺 =1 Context Sensitive Grammar 左辺右辺 Turing Machine なんでもあり

32 具体的に言語を定義する簡単な式を定義する lines : lines expr ' n' lines 'n' ; expr : expr '+' term term ; term : term '*' factor factor ; factor : '(' expr ')' DIGIT ; ここからどのような言語が生成されるかを観察してみよう Fortran 規格 p.531ff を見てみよう ( _2010.pdf) Context Free Grammar で記述されていることが観察される

33 定義の規模 XML の場合ルール 83 ( 欠番が少々あり ) Fortran2008 の場合ルール 458 制約 537

34 問題文法と具体的にひとつの文字列が与えられたときにその文字列が文法に則って生成されたかどうかをチェックせよ自明な解として文法によって生成される文字列を列挙してその中に当該文字列が含まれているかどうかをチェックするやってられない

35 通常の解文法に応じて文字列を入力として Yes/No を出力する受理機械を作る例 : ( ( ( ( ) ) ( ) ) ) Scan head スタック 1. 適当にスタックにつむ 2. ( とマッチしたらスタックにつむ 3. ヘッドが ) とマッチしたらスタックをポップして次に進む 4. 文字列の最後に来たときにスタックが空になったら OK

36 受理機械は言語の生成と逆のことを往々にしてやりますこの話 (Parse) は次々回にしますさてと

37 プログラミング言語の定義ほとんどすべてのプログラミング言語は CFG を用いて定義されます定義に用いる記法を BNF といいます BNF はこの意味でメタな意味の言語です BNF は CFG+α で定義されます

38 BNF の (+α) 部分 Syntax ::= Alt1 Alt2 ( 選択肢 ) Syntax ::= [A] B ([ ] は省略可能 A? とも ) Syntax ::= A+, A* ( 一回以上の繰り返しゼロ回以上の繰り返し ) その他にもアドホックな拡張がなされることがあります規格で使う記法については 25 ページ以降をみましょう [Notation]

39 言語はBNFだけで定義されるのではありません Document [1] document ::= ( prolog element Misc* ) - ( Char* RestrictedChar Char* ) Matching the document production implies that: It contains one or more elements. [Definition: There is exactly one element, called the root, or document element, no part of which appears in the content of any other element.] For all other elements, if the start-tag この部分は何 is? in the content of another element, the end-tag is in the content of the same element. More simply stated, the elements, delimited by start- and end-tags, nest properly within each other. [Definition: As a consequence of this, for each nonroot element C in the document, there is one other element P in the document such that C is in the content of P, but is not in the content of any other element that is in the content of P. P is referred to as the parent of C, and C as a child of P.]

40 文法 + 制約条件が言語の定義のこつです制約条件を軽視してはいけませんここに CFG だけでは記述しきれないさまざまなルールが自然言語で記述されています文法部分をシンプルに保ちながら自然言語の記述力を活かす事でプログラミング言語の定義の手法は完成しました ( 制約が守られているかどうかのチェックにはチェック用のプログラムを書くことが必要になります )

41 言語の規格ではちょっと読んでみましょうすぐつまりますなぜ? 規格で使う独特の言い回しについては最初に解説がありますここを軽視してはいけません RFC2119 規格ローカルな言い回しの定義は最初のほうに記述があります

42 言語の規格の読み方規格の書かれ方概念の定義 Syntaxの定義制約 Well-formedness constraint Validity constraint 解説

43 Syntax は BNF で書く例 : [39] element ::= EmptyElemTag STag content ETag [WFC: Element Type Match] [VC: Element Valid] 例えば以下のものが element になる <a href= a.html > Tab </a>

44 すると STAG は < ではじまって実際 [40] STag ::= < Name (S Attribute)* S? > [WFC: Unique Att Spec]

45 Content は element を含むデータの列で ETAG は実際 [43] content ::= CharData? ((element Reference CDSect PI Comment) CharData?)* [42] ETag ::= '</' Name S? '>'

46 STAG と ETAG に関する制約がさらに加わる Well-formedness constraint: Element Type Match The Name in an element's end-tag MUST match the element type in the start-tag.

47 憶えるべきことはこれですべてあとは理解力と想像力

48 JIS 規格でも話はほとんど一緒 Fortran の文法はどう定義されているか Fortra2008 Fortran2008 は 458 のルールと 537 の制約で定義されている CF. Fortran2003 は 411 のルールと 468 の制約で定義されている ( 規格は必ず膨張する ) (XML のルールは 83)

49 今回のまとめ言語を定義するには CFG+ 制約を用います規格の読み方にはこつがあります定義されているものは概念と文法と意味あとは理解力と想像力 Fortran は 458 のルールと 537 の制約で定義されています

仕様とは? 規格とは? 仕様 (Specification): ( 言語が ) みたすべき要求事項の集合規格 (Standard): ( 複数の仕様の ) 相互運用のために市場である権威のもとに調整された仕様この講義で本来問題になるのは仕様ただし規格が問題になるのは言うまでもない

プログラミング言語処理系論 (3) Design and Implementation of Programming Language Processors 佐藤周行 ( 情報基盤センター / 電気系専攻融合情報学コース ) 仕様とは? 規格とは? 仕様 (Specification): ( 言語が ) みたすべき要求事項の集合規格 (Standard): ( 複数の仕様の ) 相互運用のために市場である権威のもとに調整された仕様