Compiler Construction Quizlet

Every compiler converts a \_____ program to a \_____ program

source

What type of compilers do many Java interpreters use?

just-in-time

What do macros get converted into?

source language statements

What does the assembler do?

converts assembly code into machine code

What are the two main parts of a compiler?

analysis and synthesis

What does the analysis part of the compiler pass to the synthesis part?

a symbol table and intermediate representation

The synthesis part of a compiler is also called the \_____

back end

The symbol table is...

used by all phases of the compiler

Another name for scanning is

lexical analysis

Another name for parsing is...

syntax analysis

In a syntax tree an interior node represents...

an operation

During what stage of analysis is the syntax tree built?

syntax analysis

In what stage of analysis does type checking occur?

semantic analysis

How can we support multiple target machines for a single source language?

develop multiple backends

What is the most important objective of compiler optimizations?

correctness

What do finite-state machines and regular expressions model?

keywords and identifiers

What is true of programming language features that make programming easier?

they incur run-time overhead

What can be found in most computers both at the instruction level and at the processor level?

parallelism

What is the most important problem in optimizing a program?

using registers effectively

What maps names to locations (variables) in memory (the store)?

environment

What maps memory locations to values?

state

A procedure...

is like a function but doesn't return a value

The proper form of a program is called...

syntax

What a program means is called...

semantics

Sytnax trees and three-address code are both

intermediate representations

In a context free grammar the -\> in A -\> B(C) means...

can have the form

In a grammer A -\> B(C) is called a...

production

In a grammer the elementary symbols

thos not defined by other symbols are called...

The left side of a production is called the...

head

What appears on the right side of grammer productions?

terminals and nonterminals

In all but trivial grammars the start symbol is a...

nonterminal

If multiple productions have the same nonterminal on the left side...

they con be combined into 1 production with the right sides separated by |

What does epsilon stand for in grammars?

the empty string

What is the input to parsing?

a string of terminals

What is the output of parsing?

a parse tree

A parse tree shows how a start symbol derives a

string in the language

The root of a parse tree is...

the start symbol

How do you show that a grammar is ambiguous?

show that a terminal string has more than one parse tree

Parse trees for left-associative oparators grow

down to the left

Precendence of operators...

can be encoded into grammars

What attaches rules or program fragments to grammar productions?

syntax directed translation.

In a sytax directed translation an attribute for a node N that can be determined by N and N's children is called....

synthesized

Program fragmenst imbedded within production boddies are...

ematic actions

What is the process of determining how a string of terminals can be generated by a grammar?

parsing

The current symbol being scanned is called...

the lookahead symbol

Sometimes there are multiple productions we could use

how do we determine if a production is not suitable?

What is FIRST(X)?

the set of symbols that appear first in the strings of terminals generated from x

Given multiple productions how does a predictive parser choose one?

comparing the FIRST of each right hand side

In a predictive parser

if a terminal in the body of a production doesn't match the lookahead

In lexical analysis

a token is...

What does the lexical analyzer allow to appear within expressions?

white space

The symbol table is constructed during \_____ and used during \_____

analysis

Parsers are better at \_____ than lexical analyzers

distinguishing between different declarations of an identifier

Technically scope refers to... (operators

identifiers

All the symbol tables for a program form a...

tree

What are the two most important intermediate representations?

linear representations and trees

Is static checking done at runtime or compile time?

compile time

Making sure that an identifier is not declared multiple times in a scope is an example of...

syntactic checking

What are two types of static checking?

syntactic checking and type checking

In the expression 2 * 3.14

converting 2 to 2.0 is an example of...

A symbol with different meanings base don its context is said to be...

overloaded

An if statement in 3 address code needs...

a jump instruction

Many compilers attempt to generate code that is as good as or better than assembly code produced by...

experts

One task of the lexical analyzer is to...

group input characters into lexemes

For what type of lexemes does the lexeme need to be added to the symbol table?

identifiers

What function on the lexical analyzer is commonly called by the parser?

getNextToken

Correlating error messages with the source program is a function of the...

lexical alyzer

What are two reasons the analysis portion of the compiler is split into lexical analysis and syntax analysis?

compiler efficiency and simplicity of design

What is a pair consisting of a token name and an optional attribute called?

a token

A pointer is generally the attribute for an identifier

why?

A proper prefix of string s....

cannot be equal to s

What do we call a language that can be defined by a regular expression?

a regular set

What does + operator represent in a regular expression?

one or more

What does ? represent in a regular expression?

one or zero

What is [a-z] shorthand for?

a|b|c|...|z

What are the nodes in a transition diagram?

states

If a transition diagram is deterministic

there is never more than one...

An accepting state is indicated by...

a double circle

The start state is indicated by...

an edge from nowhere leading to it

In a lexical analyzer each state has...

a piece of code

The set of languages recognized by DFAs and NFAs are what? (the same

NFA represents more than DFA

In an NFA

the same symbol can label edges...

In a NFA

the set of strings labeling some path from the start to an accepting state defines...

What is the difference between an NFA and a DFA?

There are no epsilon transitions

What does the parser get from the lexical analyzer?

a string of tokens

What are some kinds of parsers?

bottum-up

The input the the parser is scanned

one symbol at a time

What kind of error is a misspelling?

lexical erorr

What kind of error is a misplaced semicolon?

syntactic error

What kind of error is a mismatch between an operator and its operands?

semantic error

What kind of error is incorrect reasoning?

logical error

The simplest error recovery strategy for a parser is...

to quit on the first error

When creating a derivation each rewriting step replaces a nonterminal with

the body of a production

In generating a derivation from the start symbol what symbol what does \=\> mean?

derives in one step

Given a \=\> b \=\> c what is true?

a derives c

In a parse tree what does each interior node represent?

the application of a production

If more than one leftmost derivation for a sentence exists then

the grammar is ambiguous

What is the relationship between grammars and regular expression? (They are as expressive as each other

regular expressions are more expressive than grammars

Which of the following languages cannot be accepted by a finite automaton? ab^n

a^nb^n

Bottom-up parsing can be though of as...

reducing a string to the start symbol