2-10 Grammars

Question 1

Syntax

Answer 1

the form or structure of the code (expressions, statements, program units)

Question 2

Semantics:

Answer 2

the meaning of the code (what does each statement do?)

Question 3

Alphabet:

Answer 3

What characters can constitute a program (C++: letters, numbers,
symbols: ()[]{}.,;+=-*/, whitespace: space, tab, return, eof)

Question 4

Sentence

Answer 4

: string of characters from the alphabet

Question 5

Language

Answer 5

: set of sentences

Question 6

Lexeme

Answer 6

: the lowest level syntactic unit of a language (if, (, continue, ), etc.)

Question 7

Token

Answer 7

category of lexeme: (keyword, punctuation, identifier, punctuation,
punctuation, identifier, operator, integer literal, punctuation, etc.)

Question 8

DFA’s and NFA’s

Answer 8

recognize a language

Question 9

Grammars

Answer 9

define the rules of a language

Question 10

Regular Grammars

Answer 10

• Can be right-linear or left-linear
• Generate regular languages
• Accepted by DFA’s
• Some computer languages are regular like when you use regular expressions for pattern matching

Question 11

Context-Free Grammars

Answer 11

• Generate context-free languages
• Accepted by push-down automata
• Programming languages are context free

Question 12

Context-Sensitive Grammars (Unrestricted Grammars)

Answer 12

• Generate recursively enumerable languages
• Accepted by Turing Machines

Question 13

BNF grammars are a form of

Answer 13

context-free grammars

Question 14

Grammar is ambiguous if

Answer 14

It can generate multiple parse trees

Question 15

Grammar is unambiguous if

Answer 15

it generates a single parse tree