• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
52
0
0

読み込み中.... (全文を見る)

全文

(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 1866 1995年  HTML 3.2 W3C 1997年  HTML 4.01 W3C 1999年  HTML 5 W3C 2012年  HTML 5.1  今ここ

(11)

ブラウザベンダーの規格対応

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

(12)

HTMLの規格

 現在の規格 HTML 5.1 http://www.w3.org/TR/html51/  ひとつ前のまともに定義されていた規格 HTML 4.01 http://www.w3.org/TR/html4/  これを読む?  規格はDTDで記述されている(DTDは後でやる)  プログラミング言語の標準的な定義の仕方ではな いので…

(13)

そんなことを言っても

 記述は  定義(できるだけ形式的に)  文法  追加要素  説明  自然言語で行う  定義の意図  形式的には記述できなかった何か  その他  例を含むことがある

(14)

<!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.

(15)

HTML5では

(16)

利用者の立場でなく

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

(17)

ということで今回の予定

 「規格を読む」訓練をしましょう

 テキストはXMLの定義文書

http://www.w3.org/TR/2006/REC-xml11-20060816/

 Extensible Markup Language (XML) 1_1

(Second Edition).mht

 BNFの読み方を理解しましょう

 定義の仕方

 規格独特の言い回しを理解しましょう

(18)

次回(たぶん次々回)の予定

 文法から、パーサを作る  BNFをそのまま解釈する  出力として、いろいろなものを考える  インタープリタで実行  解析木を解釈  機械語に翻訳して実行  BISON,YACCの基礎知識は不要です

(19)

What is XML?

 やみくもに規格を読んでもわかりません

(20)

<?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>

(21)

What is XML for?

 Web間/Webとブラウザ間を流れるデータの

共通フォーマットとして設計

 インターネット上のデータ流通に特化

 マークアップ言語 として定義

eXtensible Markup Language

 Webだから、「文書」の形式

 HTML

(22)

蛇足

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

(23)

具体例をいくつか

<?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

(24)

XMLの構造

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

これで、大体はわかるけど、

大体でいいの?

(25)

XMLの構造

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

(26)

XMLの仕様書

 まずは目次を見てみる  1 Introduction 2 Documents 3 Logical Structures 4 Physical Structures 5 Conformance 6 Notation

(27)

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

(28)

通常のプログラミング言語では

 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

(29)

 続き

11. Program units 12. Procedures

13. Intrinsic procedures and modules 14. Exceptions and IEEE arithmetic 15. Interoperability with C.

(30)

 大体のあたりをつけられるか?慣れれば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.

(31)

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

(32)

XMLの構造

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

(33)

簡単な例を

 言語と文法の例 S → P P → a P a P → b P b P →  言語の生成の例 S -> P -> a P a -> ab P ba -> aba P aba -> abaaba

(34)

言語のクラス

 Regular Expression

 |左辺| = 1, 右辺は terminal+non-terminalのみ

 Context Free Grammar

 |左辺|=1

 Context Sensitive Grammar

 |左辺| ≦|右辺|

 Turing Machine

(35)

具体的に言語を定義する

 簡単な式を定義する

lines : lines expr '¥n' | lines 'n'

| ;

expr : expr '+' term | term

;

term : term '*' factor | factor ; factor : '(' expr ')' |DIGIT ; ここからどのような言語が生成されるかを観察してみよう  Fortran規格 p.531ffを見てみよう(01539-01_2010.pdf)

(36)

定義の規模

 XMLの場合  ルール83 (欠番が少々あり)  Fortran2008の場合  ルール 458  制約 537

(37)

問題

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

(38)

通常の解

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

(39)

 「受理機械」は、言語の生成と逆のことを往々 にしてやります

 この話(Parse)は次々回にします

(40)

プログラミング言語の定義

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

(41)

BNFの(+α)部分

Syntax ::= Alt1 | Alt2 (選択肢)

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

(42)

 言語は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.]

(43)

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

(44)

言語の規格

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

(45)

言語の規格の読み方

 規格の書かれ方  概念の定義  Syntaxの定義  制約  Well-formedness constraint  Validity constraint  解説

(46)

 SyntaxはBNFで書く

 例:

[39] element ::=

EmptyElemTag |

STag content ETag

[WFC: Element Type Match]

[VC: Element Valid]

 例えば、以下のものがelementになる

(47)

 すると、STAGは<ではじまって…

 実際

[40] STag ::= ‘<’ Name (S Attribute)* S? ‘>’ [WFC: Unique Att Spec]

(48)

 Contentは、elementを含むデータの列で…  ETAGは…

 実際

[43] content ::= CharData? ((element |

Reference | CDSect | PI | Comment)

CharData?)*

(49)

 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.

(50)

 憶えるべきことはこれですべて

(51)

JIS規格でも話はほとんど一緒

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

(52)

今回のまとめ

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

参照

関連したドキュメント

つまり、p 型の語が p 型の語を修飾するという関係になっている。しかし、p 型の語同士の Merge

断するだけではなく︑遺言者の真意を探求すべきものであ

生物多様性の損失は気候変動とも並ぶ地球規模での重要課題で

従って,今後設計する機器等については,JSME 規格に限定するものではなく,日本産業 規格(JIS)等の国内外の民間規格に適合した工業用品の採用,或いは American

従って,今後設計する機器等については,JSME 規格に限定するものではなく,日本工業 規格(JIS)等の国内外の民間規格に適合した工業用品の採用,或いは American

従って,今後設計する機器等については,JSME 規格に限定するものではなく,日本産業 規格(JIS)等の国内外の民間規格に適合した工業用品の採用,或いは American

したがいまして、私の主たる仕事させていただいているときのお客様というのは、ここの足

 次に、羽の模様も見てみますと、これは粒粒で丸い 模様 (図 3-1) があり、ここには三重の円 (図 3-2) が あります。またここは、 斜めの線