Midterm Questions Flashcards
(25 cards)
What machine does a lexical analyzer use?
Deterministic Finite Automaton
What kind of language does a DFA recognize?
Regular Languages
What makes context free grammar ambiguous?
More than one parse tree for a string
What do we call a computer where the compiled code runs?
Target machine
What is a sentential form?
A string of terminals and non terminals
What kind of machine does a parser use?
PDA (Pushdown Automata)
Can an NFA be simulated by a DFA?
Yes
What do we call the input of the compiler?
Source program
What is the input of a lexical analyzer? Output?
Input: character stream
Output: token stream
Why do we need/use first and follow sets?
To form lookahead, to avoid backtracking
Can a regular language contain(as a proper subset of it) a non regular language?
Yes
Which parse method recognizes the most CFGs?
Generalized parsing, CYK
Does lexical analyzer need lookahead?
Yes
Why is regular expression to mDFA pipeline important?
Automates a very tedious, error prone procedure. We want automatic language translation
What are the compiler stages in order?
Lexical Analysis
Syntax Analysis
Semantic Analysis
Intermediate code generation
Code optimization
Code Generation
What were the first language translators called
Assembly language
Do parsers recognize languages or grammars?
Grammars
Chomsky Hierarchy in order:
Type 0: Recursively Enumerable
Type 1: Context Sensitive
Type 2: Context Free
Type 3: Regular Languages
Formal Definition of a DFA
5-Tuple:
(Q, Σ, δ, q0, F) states, alphabet, transition function, start, accept states
Do NFAs and DFAs (pushdown automata) recognize the same set of languages?
Yes
Do tokens partition the set of lexemes accepted by the lexical analyzer? (Think project 1)
Yes
What is the working definition of a compiler?
Turns source language into target language
What is the input and output of a syntax analyzer?
Input: token stream
Output: parse tree
What is an alphabet?
A set of characters or symbols
