[PDF] Concepts of Programming Languages - Lecture 4 - Grammars

View - Download Concepts of Programming Languages - Lecture 4 - Grammars

Previous PDF

Next PDF

Concepts of Programming Languages

Lecture 4 - Grammars

Patrick Donnelly

Montana State University

Spring 2014

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 1 / 42

Administrivia

Assignments:

Programming #1 : due 02.10

Reading:

Chapter 3

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 2 / 42 A language that is simple to parse for the compiler is also simple to parse for the human programmer.

N. Wirth (1974)

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 3 / 42

Terminology

Definition

Asentenceis a string of characters over some alphabet.Definition

Alanguageis a set of sentences.Definition

Alexemeis the lowest level syntactic unit of a language (e.g.,*, sum, begin).Definition

Atokenis a category of lexemes (e.g., identifier).Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 4 / 42

Grammars

Definition

Ametalanguageis a language used to define other languages.Definition Agrammaris a metalanguage used to define the syntax of a language.This course is interested in using grammars to define the syntax of a programming language. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 5 / 42

Context-Free Grammars

Developed by Noam Chomsky in the mid-1950s

Language generators, meant to describe the syntax of natural languages Define a class of languages called context-free languages Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 6 / 42

Backus-Naur Form (BNF)

Definition

Backus Normal Form(1959) is a stylized version of a context-free grammar (cf. Chomsky hierarchy)First used to define syntax of Algol 60

Now used to define syntax of most major languages

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 7 / 42

BNF Grammar

Definition

Nonterminalsact like syntactic variables for representing classes of syntactic structures.Definition

Terminalsare lexemes or tokens.Definition

Aproduction rulehas a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminalsDefinition

Astart symbolis a special element of the nonterminals of a grammar.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 8 / 42

BNF Grammar

Definition

Nonterminalsact like syntactic variables for representing classes of syntactic structures.Definition

Terminalsare lexemes or tokens.Definition

Aproduction rulehas a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminalsDefinition

Astart symbolis a special element of the nonterminals of a grammar.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 8 / 42

BNF Grammar

Definition

Nonterminalsact like syntactic variables for representing classes of syntactic structures.Definition

Terminalsare lexemes or tokens.Definition

Aproduction rulehas a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminalsDefinition

Astart symbolis a special element of the nonterminals of a grammar.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 8 / 42

BNF Grammar

Set ofproductions:P

terminalsymbols:T nonterminalsymbols:N startsymbols:S2N

Aproductionhas the form:

A!!

whereA2Nand!2(N[T)Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 9 / 42

Example: Binary Digits

Consider the grammar:

binaryDigit!0 binaryDigit!1 or equivalently: binaryDigit!0 | 1 where | is a metacharacter that separates alternatives. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 10 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

We can derive any unsigned integer, like352, from this grammar.Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Derivation of 352 as an Integer is a 6-step process.Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Use a grammar rule to enable each step:Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Replace a nonterminal by a right-hand side of one of its rules:Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Each step follows from the one before it:Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

You finish when there are only terminal symbols remaining.Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

Consider the grammar:

Integer!Digit | Integer Digit

Digit!0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This method was arightmost derivation.Integer!IntegerDigit !Integer2 !IntegerDigit 2 !Integer5 2 !Digit5 2 !35 2 Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 11 / 42

Derivations

An alternate derivation of352.

Integer!Integer Digit

!Integer Digit Digit !Digit Digit Digit !3 Digit Digit !3 5 Digit !3 5 2 This is called aleftmost derivation, since at each step the leftmost nonterminal is replaced. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 12 / 42

Notation for Derivations

Integer!352

Means that352can be derived in a finite number of steps using the grammar forInteger.352!L(G) Means that352is a member of the language defined by grammarG.L(G) = {!2T| Integer!!} Means that the language defined by grammarGis the set of all symbol

strings!that can be derived as anInteger.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 13 / 42

Notation for Derivations

Integer!352

Means that352can be derived in a finite number of steps using the grammar forInteger.352!L(G) Means that352is a member of the language defined by grammarG.L(G) = {!2T| Integer!!} Means that the language defined by grammarGis the set of all symbol

strings!that can be derived as anInteger.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 13 / 42

Notation for Derivations

Integer!352

Means that352can be derived in a finite number of steps using the grammar forInteger.352!L(G) Means that352is a member of the language defined by grammarG.L(G) = {!2T| Integer!!} Means that the language defined by grammarGis the set of all symbol

strings!that can be derived as anInteger.Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 13 / 42

Parse Trees

Definition

Aparse treeis a graphical representation of a derivation.Each internal node of the tree corresponds to a step in the

derivation.Each child of a node represents a right-hand side of a production. Each leaf node represents a symbol of the derived string, reading from left to right. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 14 / 42

Parse Trees

The stepInteger!Integer Digitappears in the parse tree as:Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 15 / 42

Parse Trees

Parse Tree for 352 as an Integer:

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 16 / 42

Arithmetic Expression Grammar

The following grammar defines the language of arithmetic expressions with:1-digit integers, addition, and subtraction.

Expr!Expr + Term | Expr - Term | Term

Term!0 | ...| 9 | ( Expr )Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 17 / 42

Parse Trees

Parse of the String 5-4+3:

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 18 / 42

Associativity and Precedence

A grammar can be used to define associativity and precedence among the operators in an expression.Example + and - are left-associative operators in mathematics; * and / have higher precedence than + and - .Consider the more interesting grammarG1:

Expr!Expr + Term | Expr - Term | Term

Term!Term*Factor | Term / Factor |

Term % Factor | Factor

Factor!Primary**Factor | Primary

Primary!0 | ...| 9 | ( Expr )Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 19 / 42

Associativity and Precedence

A grammar can be used to define associativity and precedence among the operators in an expression.Example + and - are left-associative operators in mathematics; * and / have higher precedence than + and - .Consider the more interesting grammarG1:

Expr!Expr + Term | Expr - Term | Term

Term!Term*Factor | Term / Factor |

Term % Factor | Factor

Factor!Primary**Factor | Primary

Primary!0 | ...| 9 | ( Expr )Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 19 / 42

Associativity and Precedence

A grammar can be used to define associativity and precedence among the operators in an expression.Example + and - are left-associative operators in mathematics; * and / have higher precedence than + and - .Consider the more interesting grammarG1:

Expr!Expr + Term | Expr - Term | Term

Term!Term*Factor | Term / Factor |

Term % Factor | Factor

Factor!Primary**Factor | Primary

Primary!0 | ...| 9 | ( Expr )Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 19 / 42

Parse of

4**2**3+5*6+7

for GrammarG1Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 20 / 42

Associativity and Precedence forG1

PrecedenceAssociativityOperators

3right**

2left* / %

1left+ -

These relationships are shown by the structure of the parse tree: highest precedence at the bottom, and left-associativity on the left at each level. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 21 / 42

Derivations

Definition

Every string of symbols in a derivation is asentential form.Definition Asentenceis a sentential form that has only terminal symbols.Definition Aleftmost derivationis one in which the leftmost nonterminal in each sentential form is the one that is expanded. Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 22 / 42

Ambiguous Grammars

Definition

A grammar isambiguousif one of its strings has two or more diffferent parse trees. e.g., Grammar G

1above is unambiguous.C, C++, and Java have a large number of

operators and precedence levels Instead of using a large grammar, we can:Write a smaller ambiguous grammar, and

Give separate precedence and associativity

Patrick Donnelly (Montana State University)Concepts of Programming LanguagesSpring 2014 23 / 42

Ambiguous Grammars

Definition

A grammar isambiguousif one of its strings has two or morequotesdbs_dbs9.pdfusesText_15

[PDF] concert djadja dinaz paris 9 novembre

[PDF] concierge key american airlines number

[PDF] concise oxford dictionary of english etymology pdf

[PDF] concise oxford english arabic dictionary pdf

[PDF] concise oxford english dictionary 11th edition free download pdf

[PDF] concise oxford english dictionary 12th edition pdf

[PDF] concise oxford english dictionary pdf

[PDF] concise oxford english dictionary pdf download

[PDF] concise rules of apa style

[PDF] concise rules of apa style 6th edition

[PDF] concise rules of apa style 6th edition pdf

[PDF] concise rules of apa style ebook

[PDF] concise rules of apa style sixth edition

[PDF] concise rules of apa style sixth edition pdf free download

[PDF] concluding paragraph