Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cs-236:project-1-worksheet [2015/01/05 21:02]
egm created
cs-236:project-1-worksheet [2015/01/05 21:06] (current)
egm
Line 1: Line 1:
-* [[Project 1 Worksheet | Project 1 Worksheet: Lexical Analysis ​for Datalog]] +The objectives ​for this project are to 
-[[Project 2 Worksheet | Project 2 WorksheetLL(1Parsing ​of Datalog]] +Create finite state machines to recognize tokens from regular expressions 
-[[Project 3 Worksheet | Project 3 WorksheetAnswering Datalog Queries]] +* Implement the state machines with a C++ program 
-[[Project 4 Worksheet | Project 4 WorksheetGenerating Facts from Datalog Rules]] +* Produce a correct stream of tokens given arbitrary input 
-[[Project 5 Worksheet | Project 5 WorksheetOptimizing Rule Evaluation ​in Datalog ​Queries]]+ 
 +==Notation and Definitions== 
 +A deterministic finite state machine is a quintuple $(S,\ I,\ f,\ s_0,\ F)$, where: 
 +* $S$ is a finite, non-empty set of states 
 +* $I$ is the input alphabet ​(a finite, non-empty set of symbols) 
 +* $f$ is the state-transition function: $f\ :\ S \times I \rightarrow S$ 
 +* $s_0$ is an initial state, an element ​of $S$ 
 +*  $F$ is the set of final states, a (possibly empty) subset of $S$. 
 +  
 +A finite state transducer is a 6-tuple $(S,\ I,\ O,\ f,\ g,\ s_0)$ as above except
 +* $O$ is the output alphabet (a finite, non-empty set of symbols) 
 +* $f$ is the state-transition function$f\ :\ S \times ​ I \rightarrow S$ 
 +* $g$ is the output function$g\ :\ S \times I \rightarrow O$ 
 + 
 +==Questions== 
 +# What is the line of code in '''​Lex.cpp'''​ that establishes <​math>​s_0</​math>?​ 
 +# Where are the elements of <​math>​S</​math>​ enumerated? ​ Give the first three as they appear in the code. 
 +# What are the elements in the set <​math>​I</​math>?​ 
 +# Describe a way to refactor the code so that it would work for any FSM, not just the one that has the structure required for the Datalog ​lexer. 
 +# The code implements the state-transition function <​math>​f\ :\ S \times I \rightarrow S</​math>​ in two different ways depending on whether a non-empty token in <​math>​O</​math>​ is to be emitted according to <​math>​g\ :\ S \times I \rightarrow O</​math>​. ​ Match the state-transition function to the code below by circling, labeling, and explaining how the code components represent the state, S, obtain the  input I, and represents the output O for the '''​Comma'''​ state and the input I and output O for the '''​SawColon'''​ state. ​  
 +# Why is there no token emitted for the '''​SawColon'''​ case in the switch statement?​ 
 + 
 +<code cpp> 
 + State Lex::​nextState() { 
 +    State result; 
 +    char character;​ 
 +    switch(state) { 
 +        case Start: ​              ​result = getNextState();​ break; 
 +        case Comma: ​              ​emit(COMMA);​ result = getNextState();​ break; 
 +        case Period: ​             emit(PERIOD);​ result = getNextState();​ break; 
 +        case SawColon: 
 +            character = input->​getCurrentCharacter();​ 
 +            if(character == '​-'​) { 
 +                result = Colon_Dash;​ 
 +                input->​advance();​ 
 +            } else { //Every other character 
 +                throw "​ERROR::​ in case SawColon:, Expecting ​ '​-'​ but found " + character + '​.';​ 
 +            } 
 +            break; 
 +      case Colon_Dash: ​         emit(COLON_DASH);​ result = getNextState();​ break; 
 + … 
 +</​code>​
cs-236/project-1-worksheet.txt · Last modified: 2015/01/05 21:06 by egm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0