Concepts of PLs Definitions Flashcards
Syntax (of a PL)
The form of its expressions, statements, and program units
Semantics (of a PL)
The meaning of the syntax (the expressions, statements, and program units)
Sentences
Also called statements; the strings of a language
Lexemes
Lowest-level syntactic units
Examples: numeric literals, operators, special words, etc.
Identifiers
A group formed by lexemes;
A token that can have lexemes, or instances
Examples: names of variables, methods, classes, etc.
Token (of a PL)
The name of a lexeme group; a category of its lexemes
Recognition
–
Generation
Grammars
The formal language generation mechanisms
Backus-Naur Form (BNF)
- 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
Context-free grammars
Metalanguage
A language used to describe another language
Left-hand side (LHS)
The abstraction being defined; text left side of the arrow
Right-hand Side (RHS)
The definition of the LHS; consists of some mixture of tokens, lexemes, references to other abstracts
Rule (production)
LHS -> RHS; the total definition
Nonterminal symbols (nonterminals)
The abstractions in a BNF description, or grammar
Terminal symbols (terminals)
The lexemes and tokens of the rules
Grammar (BNF description)
A collection of rules
Note: a grammar is also called BNF
What does BNF use for syntactic structures?
Abstractions
Abstraction (in a BNF description)
(also, NONTERMINAL SYMBOLS)
(Also, NONTERMINALS)
• 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
What is the following symbol called: | ?
Logical OR
The following is an example of a BNF of the Java if statement. Fill in the remaining syntax.
→ ( )
→ ( ) else
stmt
What can BNF describe?
BNF can describe nearly all of the syntax of PLs because it is sufficiently powerful
Rewrite the following BNF description using logical or:
→ if ( )
→ if ( ) else
→ if ( )
| if ( ) else
Finish the definition of recursion:
A rule is recursive if _________________________________.
Its LHS appears in its RHS
What does the following rule illustrate?
→ identifier | identifier,
How BNF uses recursion to describe lists
What is in the following example?
→ identifier | identifier,
is either:
- a single token (identifier) OR
- an identifier followed by a comma and another instance of
