プログラミング言語処理系論
(3)
Design and Implementation of
Programming Language Processors
佐藤周行
(情報基盤センター/電気系専攻融合情報学
仕様とは?規格とは?
仕様(Specification): (言語が)みたすべき 要求事項の集合 規格(Standard): (複数の仕様の)相互運 用のために市場である権威のもとに調整され た仕様 この講義で本来問題になるのは「仕様」ただし、 「規格」が問題になるのは言うまでもない前回の講義で述べたこと
(現象面からの観察として)プログラミング言語 処理系の実装が複数出てくると、規格の必要 性が議論されるようになります 規格を作るモチベーションとしてはいろいろな ものがあります(善意から邪悪まで) プログラミング言語は「仕様」「規格」が問題に なる重要な分野です実は
…
「仕様」「規格」が重要な意味を持つもう一つの 分野として「ネットワーク」があります 「プロトコル(通信規格)」「相互運用性」が常に 問題になってきました L1からL7まで、常に。 ISOやITUなど、伝統的な規格作成の場の他 にIETFが大きな役割をもっています RFC プログラミング言語の仕様を読めるようにする わけですが どのような書き方に従っているのか 特定の意味を持つ語がどのくらい使われているの か 等々を実感するのに、最初から大部な規格書を読 むのは少し荷が重い というわけで、ネットワークに関係する文書か ら簡単なものを少し引っ張ってきます。
今までプログラミング言語で講義した来たこと をHTTP+HTMLでやってみます ブラウザがHTMLを「正しく理解」できない時点で アウト ブラウザとWebサーバがHTTPを「正しく理解」で きない時点でアウト 「アウト」=処理が正しく行われない
HTMLの仕様と言って思うものは何?
利用者 (プログラマ) ブラウザ (処理系) HTML文書 (プログラム) サーバ「正しい」
HTML文書とは?
ブラウザが「正しく」表示できればそれは「正し
い」HTML文書か?
どのブラウザで表示できれば正しいHTML文
書か?
IE, FireFox, Safari, Opera, …
あるブラウザ「だけ」で正しく表示されなくない
HTML文書があったとき、悪いのはHTML文 書か、ブラウザか?
Webの市場の大きさ
WebブラウザのHTML文書の仕様の解釈が 大きな力を持つ ビジネスの力 共通の理解がないと次のようなことが平気でおき る 便利な機能を相手に黙って実装 「この仕様を持つHTML文書はこのブラウザで表示可 能」とうたう HTML仕様の世界の支配規格
HTMLの規格の歴史 HTML 1.0以前 HTML 1.0 IETF より。1993年 HTML 2.0 IETF RFC 1866 1995年 HTML 3.2 W3C 1997年 HTML 4.01 W3C 1999年 HTML 5 W3C 2012年 HTML 5.1 今ここブラウザベンダーの規格対応
IE 5 HTML 4.01対応 IE5は、HTML独自拡張部分が多く、開発者を悩 ませた(らしい) Netscape Navigator 4は、レンダリングの点で IEとの「不整合」が存在した 現在は、規格への整合性を求める声が強く、 「行儀の悪い」仕様は少なくなっている 開発者を含む市場の声はやはり大きいHTMLの規格
現在の規格 HTML 5.1 http://www.w3.org/TR/html51/ ひとつ前のまともに定義されていた規格 HTML 4.01 http://www.w3.org/TR/html4/ これを読む? 規格はDTDで記述されている(DTDは後でやる) プログラミング言語の標準的な定義の仕方ではな いので…そんなことを言っても
記述は 定義(できるだけ形式的に) 文法 追加要素 説明 自然言語で行う 定義の意図 形式的には記述できなかった何か その他 例を含むことがある<!ELEMENT HEAD O O (%head.content;) +(%head.misc;) -- document head -->
<!ATTLIST HEAD %i18n; -- lang, dir -- profile %URI; #IMPLIED -- named dictionary of meta info -- >
Start tag: optional, End tag: optional Attribute definitions profile = uri [CT]
This attribute specifies the location of one or more meta data profiles, separated by white space. For future
extensions, user agents should consider the value to be a list even though this specification only considers the first URI to be significant. Profiles are discussed below in the section on meta data.
Attributes defined elsewhere
•lang (language information), dir (text direction)
The HEAD element contains information about the current
document, such as its title, keywords that may be useful to search engines, and other data that is not considered document content. User agents do not generally render elements that appear in the HEAD as content. They may, however, make information in the HEAD available to users through other mechanisms.
HTML5では
利用者の立場でなく
開発者の立場に立ってみる 何を作ったらよいのか決められていないのは困る とにかく決めてくれ 「何かを決めている文書」が、解釈に幅がある文 書だと困る 「私の解釈」が正しいことを誰か保証してくれ 自然言語で書く場合、解釈の曖昧さは宿命的ということで今回の予定
「規格を読む」訓練をしましょう
テキストはXMLの定義文書
http://www.w3.org/TR/2006/REC-xml11-20060816/
Extensible Markup Language (XML) 1_1
(Second Edition).mht
BNFの読み方を理解しましょう
定義の仕方
規格独特の言い回しを理解しましょう
次回(たぶん次々回)の予定
文法から、パーサを作る BNFをそのまま解釈する 出力として、いろいろなものを考える インタープリタで実行 解析木を解釈 機械語に翻訳して実行 BISON,YACCの基礎知識は不要ですWhat is XML?
やみくもに規格を読んでもわかりません
<?xml version="1.0" ?> <!-- 住所録 --> - <addressbook> - <personal number="0001"> <name>Aさん</name> <address>神奈川県</address> <tel>00-0000-0000</tel> <email addr="xxx@xxx.xx.xx" /> </personal> - <personal number="0002"> <name>Bさん</name> <address>東京都</address> <tel>11-1111-1111</tel> <email /> </personal> </addressbook>
What is XML for?
Web間/Webとブラウザ間を流れるデータの
共通フォーマットとして設計
インターネット上のデータ流通に特化
マークアップ言語 として定義
eXtensible Markup Language
Webだから、「文書」の形式
HTML
蛇足
実質的には タグ <address> … </address>, <h1>…</h1>など マークアップ 文書に関するメタな情報の指定(もともとは編 集用語) 段落指定、フォントサイズ指定などを行なう 指定するものをタグという具体例をいくつか
<?xml version="1.0" ?><!-- 住所録 -->
<!DOCTYPE addressbook SYSTEM "addressbook.dtd"> <addressbook> <personal number="0001"> <name>Aさん</name> <address>神奈川県</address> <tel>00-0000-0000</tel> <email addr="xxx@xxx.xx.xx"/> </personal> <personal number="0002"> <name>Bさん</name> <address>東京都</address> <tel>11-1111-1111</tel> <email/> </personal> </addressbook>
<!ELEMENT addressbook (personal*)> <!ELEMENT personal
(name,address,tel,email)> <!ATTLIST personal number CDATA
#REQUIRED>
<!ELEMENT name (#PCDATA)> <!ELEMENT address (#PCDATA)> <!ELEMENT tel (#PCDATA)>
<!ELEMENT email EMPTY> <!ATTLIST email addr CDATA
XMLの構造
<tag>ではじまり、</tag/>でおわる HTMLは違うけど、XMLでは許されないか? <tag/>ってなに? <tag a=“abc”>と中に何かを書くことができ る “abc”は引用符で囲まなければならないのか? HTMLでは違うぞ タグはネストしてよいこれで、大体はわかるけど、
大体でいいの?
XMLの構造
言語を定義するときの標準的な手法を説明す る 何を定義すると言語が定義されるのか? 言語の構造(Syntaxを含む) 言語の解釈(Semantics) どのように定義すると「定義」になるのか? BNF 定義の手法に標準的な方法はあるか? 言い回しXMLの仕様書
まずは目次を見てみる 1 Introduction 2 Documents 3 Logical Structures 4 Physical Structures 5 Conformance 6 Notation ここからわかること XMLは、Documentを定めている XMLには、Logical StructureとPhysical Structureがある Notationがあるということは、わからない表記が あったらこの章を見ればよいということだな
通常のプログラミング言語では
Fortran2008
1. 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
続き
11. Program units 12. Procedures
13. Intrinsic procedures and modules 14. Exceptions and IEEE arithmetic 15. Interoperability with C.
大体のあたりをつけられるか?慣れれば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.
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
XMLの構造
形式文法の理論を用いる(Chomsky et.al.) 言語を生成する規則の集合(文法)を与える S1 S2 S3…Sn → T1 T2 … Tm 左辺にマッチした記号列を規則→を用いて右辺に変換する 記号には、これ以上の変換ができない終端記号と、そうで ない非終端記号がある 有限回の変換で終端記号の列を生成する 生成される列の集合を「言語」という簡単な例を
言語と文法の例 S → P P → a P a P → b P b P → 言語の生成の例 S -> P -> a P a -> ab P ba -> aba P aba -> abaaba言語のクラス
Regular Expression
|左辺| = 1, 右辺は terminal+non-terminalのみ
Context Free Grammar
|左辺|=1
Context Sensitive Grammar
|左辺| ≦|右辺|
Turing Machine
具体的に言語を定義する
簡単な式を定義する
lines : lines expr '¥n' | lines 'n'
| ;
expr : expr '+' term | term
;
term : term '*' factor | factor ; factor : '(' expr ')' |DIGIT ; ここからどのような言語が生成されるかを観察してみよう Fortran規格 p.531ffを見てみよう(01539-01_2010.pdf)
定義の規模
XMLの場合 ルール83 (欠番が少々あり) Fortran2008の場合 ルール 458 制約 537問題
文法と、具体的にひとつの文字列が与えられ たときに、その文字列が文法に則って生成さ れたかどうかをチェックせよ 自明な解として、「文法によって生成される文 字列を列挙して、その中に当該文字列が含ま れているかどうかをチェックする」 やってられない通常の解
文法に応じて、文字列を入力として、Yes/No を出力する「受理機械」を作る 例: ( ( ( ( ) ) ( ) ) ) … スタック Scan head 1. 適当にスタックにつむ 2. ‘(’とマッチしたら、 スタックにつむ 3. ヘッドが’)’とマッチしたらスタックを ポップして次に進む 4. 文字列の最後に来たときに スタックが空になったらOK 「受理機械」は、言語の生成と逆のことを往々 にしてやります
この話(Parse)は次々回にします
プログラミング言語の定義
ほとんどすべてのプログラミング言語は、CFG を用いて定義されます 定義に用いる記法をBNFといいます。BNFは この意味でメタな意味の言語です BNFは CFG+α で定義されますBNFの(+α)部分
Syntax ::= Alt1 | Alt2 (選択肢)
Syntax ::= [A] B ([ ] は省略可能 A?と も) Syntax ::= A+, A* (一回以上の繰り返し、 ゼロ回以上の繰り返し) その他にも、アドホックな拡張がなされることがあ ります。規格で使う記法については25ページ 以降をみましょう [Notation]
言語は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
non-root 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.]
文法+制約条件が言語の定義のこつです 「制約条件」を軽視してはいけません。ここにCFG だけでは記述しきれないさまざまなルールが自然 言語で記述されています 文法部分をシンプルに保ちながら、自然言語の記 述力を活かす事で、プログラミング言語の定義の 手法は完成しました(制約が守られているかどう かのチェックにはチェック用のプログラムを書くこと が必要になります)
言語の規格
では、ちょっと読んでみましょう すぐつまります。なぜ? 規格で使う独特の言い回しについては、最初に解説 があります。ここを軽視してはいけません RFC2119 規格ローカルな言い回しの定義は最初のほうに記述 があります。言語の規格の読み方
規格の書かれ方 概念の定義 Syntaxの定義 制約 Well-formedness constraint Validity constraint 解説 SyntaxはBNFで書く
例:
[39] element ::=
EmptyElemTag |
STag content ETag
[WFC: Element Type Match]
[VC: Element Valid]
例えば、以下のものがelementになる
すると、STAGは<ではじまって…
実際
[40] STag ::= ‘<’ Name (S Attribute)* S? ‘>’ [WFC: Unique Att Spec]
Contentは、elementを含むデータの列で… ETAGは…
実際
[43] content ::= CharData? ((element |
Reference | CDSect | PI | Comment)
CharData?)*
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.
憶えるべきことはこれですべて