Attribute Grammars: Example 3.6Rule 1
Syntax rule: (語法規則) <assign> <var> = <expr>
Semantic rules: (語意規則) <expr>.expected_type <var>.actual_type
Determined by the type of variable on the left side of the assignment statement 由分配表示式的左邊的變數型態決定
Programming Language (程式語言) Chapter 3
Describing Syntax and Semantics (描述語法與語意)
Topics
Introduction
The General Problem of Describing Syntax
Formal Methods of Describing Syntax
Attribute Grammars
Describing the Meanings of Programs: Dynamic Semantics
Introduction
Syntax (語法)
The form or structure of the expressions (符號), statements (敘述), and program units
Semantics (語意)
The meaning of the expressions, statements, and program units
Syntax and semantics provide a language’s definition
Users of a language definition
Other language designers
Implementers
Programmers (the users of the language)
The General Problem of Describing Syntax: Terminology (術語)
A sentence is a string of characters over some alphabet (字符)
A language is a set of sentences
A lexeme (詞彙) is the lowest level syntactic (句法的) unit of a language (e.g., *, sum, begin)
A token (符號) is a category of lexemes (e.g., identifier)
Recognizers (識別器)
A recognition device reads input strings of the language and decides whether the input strings belong to the language
Example: syntax analysis part of a compiler
Detailed discussion in Chapter 4
Generators (產生器)
A device that generates sentences of a language
One can determine (測定) if the syntax of a particular (特別的) sentence is correct by comparing it to the structure of the generator
Formal Methods of Describing Syntax
Backus-Naur Form (BNF) and Context-Free Grammars (上下文無關文法)
Most widely known method for describing programming language syntax
Extended BNF
Improves readability and writability of BNF
Grammars and Recognizers
Context-Free Grammars
Developed by Noam Chomsky in the mid-1950s
Define a class of languages called context-free languages
Backus-Naur Form (BNF)
Backus-Naur Form (1959)
Invented by John Backus to describe ALGOL 58
BNF is equivalent (等同) to context-free grammars
BNF is a metalanguage (元語言) used to describe another language
In BNF, abstractions (抽象名稱) are used to represent classes of syntactic structures--they act like syntactic variables (also called nonterminal (非終端) symbols)
BNF Fundamentals (基礎)
Non-terminals
BNF abstractions (抽象名稱)
Terminals
Lexemes (詞彙) and tokens (符號)
Grammar
A collection of rules
BNF Fundamentals (基礎)
Be defined
→
Non-terminal symbol
< symbol>
Terminal symbol
symbol
Or
|
Examples of BNF rules:
→ identifier | identifier, → if then
BNF Rules
A rule has a left-hand side (LHS) and a right-hand side (RHS), and consists of terminal and nonterminal symbols
A grammar is a finite (有限的) nonempty set of rules
An abstraction (or nonterminal symbol) can have more than one RHS
| begin end
Describing Lists (描述列表)
Syntactic (句法) lists are described using recursion (遞迴)
ident
| ident,
A sentence generation is called a derivation 句子的產生稱為語言的衍生
A derivation (語言的衍生) is a repeated application (反覆應用) of rules, starting with the start symbol and ending with a sentence (all terminal symbols)
An Example Grammar
| ; = a | b | c | d
+ | - | const
statement (敘述)
variable (變數)
expression (表示式)
terminal (端點)
An Example Derivation (語言的衍生)
=> =>
=> =
=> a =
=> a = +
=> a = +
=> a = b +
=> a = b + const
Derivation
Each of the strings in the derivation is called a sentential form 每一個字串在語言的衍生中稱為句型
A sentence is a sentential form that has only terminal symbols 句子是一個只有終端符號的句型
A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded (展開、擴充)
In addition to leftmost, a derivation may be rightmost or in an order that is neither leftmost nor rightmost
Parse Tree (分析樹)
= + a b const a = b + const A hierarchical representation of a derivation
Ambiguity (模稜兩可) in Grammars
A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees 如果產生的句型可以有兩個或兩個以上的分析樹表示文法模稜兩可
Comments