Describing Syntax

Question 1

Sentence

Answer 1

A string of characters over some alphabet or finite set of symbols.

Question 2

Language

Answer 2

A set of sentences.

Question 3

Lexeme

Answer 3

The lowest level of a syntactic unit of a language. Are often not included in the formal description of the syntax of a programming language. Lexemes are divided into groups, each group receiving a token.

Question 4

Token

Answer 4

A category of lexemes, e.g. an identifier.

Question 5

Lexical analysis

Answer 5

The process of recognizing lexemes.

Question 6

What are the lexemes in the line:
index = 2 * count + 17;

Answer 6

index, = , 2, *, count, +, 17, ;

Question 7

What are the tokens in the line:
index = 2 * count + 17;

Answer 7

identifier, equal_sign, int_literal, multi_op, identifier, plus_op, int_literal, semicolon

Question 8

Recognizers

Answer 8

Reads input strings over the alphabet of the language and decides whether the input string belong to the language. The syntax analyzer part of the compiler is a recognizer.

Question 9

Generator

Answer 9

A device that generates sentences of a language. One can determine if the syntax of a sentence is correct if it could be made by a generator.

Question 10

Formal Grammar

Answer 10

A set of rules for rewriting strings, along with a “start symbol” from which rewriting starts. Therefore, a grammar is usually thought of as a language generator.

Question 11

What are the four basic formal rules for string patterns?

Answer 11

Concatenation, Alternation, Kleene Closure, and Recursion.

Question 12

Concatenation

Answer 12

The adding of strings.

Question 13

Alternation:

Answer 13

Choice among a finite number of alternatives.

Question 14

Kleene Closure:

Answer 14

Repetition an arbitrary number of times.

Question 15

Recursion:

Answer 15

Creation of a construct from simpler instances of the same construct.

Question 16

Regular Languages

Answer 16

A set of strings that can be defined by the first three rules of string patterns, and are generated by regular expressions.

Question 17

Context Free Language (CFL)

Answer 17

Any set of strings that can be defined if we add recursion and are generated by context-free grammars.

Question 18

Context-Free Grammars

Answer 18

Developed by Noam Chomsky in the mid 1950s, they are language generators meant to describe the syntax of natural languages.

Question 19

Backus-Naur Form (BNF)

Answer 19

Invented by John Backus in 1959 to describe the syntax of Algol 58 and later modified by Peter Naur to describe Algol 60. BNF is equivalent to context-free grammars.

Question 20

Metalanguage

Answer 20

A language used to define another language. BNF is a metalanguage.

Question 21

Abstractions

Answer 21

Used to represent classes of syntactic structures and act like syntactic variables. They are also called nonterminal symbols. Can have more than one RHS.

Question 22

Terminals

Answer 22

Lexemes and tokens not defined in terms of other terminals or non-terminals. Non-terminals are enclosed in angle brackets.

Question 23

Rule/Production

Answer 23

Has a LHS that is nonterminal and a RHS that is terminal and/or nonterminals.

Question 24

Define Context-Free Grammar G:

Answer 24

A tuple of elements (S, N, T, P) where S is a start symbol, T is a set of terminals, N is a set of non-terminals, and P is a finite non-empty set of rules.

Question 25

How are syntactic lists described?

Answer 25

Using recursion.

Question 26

What is a Grammar?

Answer 26

A generative device for defining languages.

Question 27

What is a Derivation?

Answer 27

A repeated application of the rules, starting with a start symbol and ending with a sentence (all terminal symbols).

Question 28

Describe BNF notation.

Answer 28

Non-terminals have angle brackets < >. Symbols without angle brackets are terminals. "-->", "::=", or ":=" means "is defined as." When rules are written X -> Y, X is the LHS and Y is the RHS.

Question 29

What symbol is used to represent an empty string?

Answer 29

The lowercase sigma symbol.

Question 30

Sentential Form

Answer 30

Every string of symbols in a derivation is of this form. A sentence, for example, is a sentential form with only terminals.

Question 31

Leftmost Derivation

Answer 31

A derivation where the leftmost non-terminal is expanded first.

Question 32

Parse Trees

Answer 32

Represents the derivation steps for the hierarchal structures where each internal node is a non-terminal and each leaf is a terminal. The in-order traversal of the tree is a representation of the statement that was parsed, and the traversal of the tree for execution is post-order.

Question 33

When is a grammar ambiguous?

Answer 33

If and only if it generates a sentential form with two or more distinct parse trees. If the grammar generates a sentence with more than one leftmost or rightmost derivation, then it is ambiguous.

Question 34

How to prevent ambiguity with operators?

Answer 34

If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity.

Question 35

Can a grammar rule have associativity?

Answer 35

Yes, operator associativity can be indicated by a grammar rule. Left recursion specifies left associativity, whereas right recursion specifies right associativity.

Question 36

Extended BNF (EBNF)

Answer 36

Does not enhance the power of BNF but increases readability and writability. Optional parts are placed in brackets [], alternate parts of RHSs are placed inside parenthesis and separated with vertical bars, repetitions are put inside braces {}, and terminals that are grammar symbols are enclosed in quotes ''.

Question 37

Is there a standard for EBNF?

Answer 37

Yes, the standard EBNF, ISO/IEC 14997:1996 exists but is rarely used.

Question 38

How do you convert from BNF to EBNF?

Answer 38

Look for recursion in grammar and common strings that can be factored out with grouping and options, then apply EBNF rules.

Question 39

How do you convert from EBNF to BNF?

Answer 39

Look for brackets and braces, then apply the normal BNF rules.

Question 40

What are some recent variations in EBNF?

Answer 40

Alternative RHSs are put on separate lines, non-terminals begin with uppercase letters (replacing <>), use of the colon instead of ->, use of the subscript opt for optional parts, and the use of oneof for choices.

Question 41

Regular Grammar

Answer 41

A simple scheme for using rules that represent strings to recognize. They are the simplest and least powerful of the grammars; they cannot recognize all patterns in general, such as paired items.

Question 42

Regular Expressions

Answer 42

A notation for representing patterns of characters.

Question 43

Where can regular expressions be found?

Answer 43

String finding in editors, pattern expansion built into command interpreters through consoles, regex libraries in java and python, and string types with built in regular expression matching (such as reg expressions in Perl).

Question 44

What are the two types of characters in a regular expression?

Answer 44

A character in a regular expression is either a regular character or a metacharacter.

Question 45

Metacharacter

Answer 45

A character that stands for something else. E.g. '.' is a metacharacter that means "matches any single character in the string." Placing a backslash before the metacharacter changes it into a regular character.

Question 46

What is the regular expression for an identifier?

Answer 46

[a-z_A-Z][0-9a-zA-Z]*

Question 47

What is the regular expression for an octal constant?

Answer 47

0[0-7]+

Question 48

What is the regular expression for a hex constant?

Answer 48

0x[0-9a-fA-F]+

Question 49

What is the regular expression for a floating point number?

Answer 49

[+-]?([0-9]*\.[0-9]+)e[+-][0-9]

Question 50

Can the matching of strings to regular expressions be automated?

Answer 50

Yes. There are libraries that compile regular expressions and match them to strings. In fact, there is a tool called lex (or flex) that uses regular expressions to create a lexical analyzer for a compiler/interpreter. The matcher is a finite state machine.