Concepts of PLs Definitions

Question 1

Syntax (of a PL)

Answer 1

The form of its expressions, statements, and program units

Question 2

Semantics (of a PL)

Answer 2

The meaning of the syntax (the expressions, statements, and program units)

Question 3

Sentences

Answer 3

Also called statements; the strings of a language

Question 4

Lexemes

Answer 4

Lowest-level syntactic units

Examples: numeric literals, operators, special words, etc.

Question 5

Identifiers

Answer 5

A group formed by lexemes;
A token that can have lexemes, or instances

Examples: names of variables, methods, classes, etc.

Question 6

Token (of a PL)

Answer 6

The name of a lexeme group; a category of its lexemes

Question 7

Recognition

Answer 7

–

Question 8

Generation

Question 9

Grammars

Answer 9

The formal language generation mechanisms

Question 10

Backus-Naur Form (BNF)

Answer 10

• a way to describe syntax of a PL
• uses natural notation
• nearly identical to context free grammars (also, just “grammars”)
• “BNF” and “grammar” are used interchangeably
• a metalanguage for PLs

Question 11

Context-free grammars

Question 12

Metalanguage

Answer 12

A language used to describe another language

Question 13

Left-hand side (LHS)

Answer 13

The abstraction being defined; text left side of the arrow

Question 14

Right-hand Side (RHS)

Answer 14

The definition of the LHS; consists of some mixture of tokens, lexemes, references to other abstracts

Question 15

Rule (production)

Answer 15

LHS -> RHS; the total definition

Question 16

Nonterminal symbols (nonterminals)

Answer 16

The abstractions in a BNF description, or grammar

Question 17

Terminal symbols (terminals)

Answer 17

The lexemes and tokens of the rules

Question 18

Grammar (BNF description)

Answer 18

A collection of rules

Note: a grammar is also called BNF

Question 19

What does BNF use for syntactic structures?

Answer 19

Abstractions

Question 20

Abstraction (in a BNF description)
(also, NONTERMINAL SYMBOLS)
(Also, NONTERMINALS)

Answer 20

• can have two or more distinct definitions, representing 2+ possible syntactic forms in the language
• these multiple definitions can be written as a single rule, with the different definitions separated by “|” (“logical OR)
Pointed brackets are often used to delimit names of abstractions

Question 21

What is the following symbol called: | ?

Answer 21

Logical OR

Question 22

The following is an example of a BNF of the Java if statement. Fill in the remaining syntax.

→ ( )
→ ( ) else

Answer 22

stmt

Question 23

What can BNF describe?

Answer 23

BNF can describe nearly all of the syntax of PLs because it is sufficiently powerful

Question 24

Rewrite the following BNF description using logical or:

→ if ( )
→ if ( ) else

Answer 24

→ if ( )

| if ( ) else

Question 25

Finish the definition of recursion:

A rule is recursive if _________________________________.

Answer 25

Its LHS appears in its RHS

Question 26

What does the following rule illustrate?

→ identifier | identifier,

Answer 26

How BNF uses recursion to describe lists

Question 27

What is in the following example?

→ identifier | identifier,

Answer 27

is either:

• a single token (identifier) OR
• an identifier followed by a comma and another instance of