Welcome to TiddlyWiki created by Jeremy Ruston, Copyright © 2007 UnaMesa Association
Background: #fff
Foreground: #000
PrimaryPale: #8cf
PrimaryLight: #18f
PrimaryMid: #04b
PrimaryDark: #014
SecondaryPale: #ffc
SecondaryLight: #fe8
SecondaryMid: #db4
SecondaryDark: #841
TertiaryPale: #eee
TertiaryLight: #ccc
TertiaryMid: #999
TertiaryDark: #666
Error: #f88
/*{{{*/
body {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}
a {color:[[ColorPalette::PrimaryMid]];}
a:hover {background-color:[[ColorPalette::PrimaryMid]]; color:[[ColorPalette::Background]];}
a img {border:0;}
h1,h2,h3,h4,h5,h6 {color:[[ColorPalette::SecondaryDark]]; background:transparent;}
h1 {border-bottom:2px solid [[ColorPalette::TertiaryLight]];}
h2,h3 {border-bottom:1px solid [[ColorPalette::TertiaryLight]];}
.button {color:[[ColorPalette::PrimaryDark]]; border:1px solid [[ColorPalette::Background]];}
.button:hover {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::SecondaryLight]]; border-color:[[ColorPalette::SecondaryMid]];}
.button:active {color:[[ColorPalette::Background]]; background:[[ColorPalette::SecondaryMid]]; border:1px solid [[ColorPalette::SecondaryDark]];}
.header {background:[[ColorPalette::PrimaryMid]];}
.headerShadow {color:[[ColorPalette::Foreground]];}
.headerShadow a {font-weight:normal; color:[[ColorPalette::Foreground]];}
.headerForeground {color:[[ColorPalette::Background]];}
.headerForeground a {font-weight:normal; color:[[ColorPalette::PrimaryPale]];}
.tabSelected{color:[[ColorPalette::PrimaryDark]];
background:[[ColorPalette::TertiaryPale]];
border-left:1px solid [[ColorPalette::TertiaryLight]];
border-top:1px solid [[ColorPalette::TertiaryLight]];
border-right:1px solid [[ColorPalette::TertiaryLight]];
}
.tabUnselected {color:[[ColorPalette::Background]]; background:[[ColorPalette::TertiaryMid]];}
.tabContents {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::TertiaryPale]]; border:1px solid [[ColorPalette::TertiaryLight]];}
.tabContents .button {border:0;}
#sidebar {}
#sidebarOptions input {border:1px solid [[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel {background:[[ColorPalette::PrimaryPale]];}
#sidebarOptions .sliderPanel a {border:none;color:[[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel a:hover {color:[[ColorPalette::Background]]; background:[[ColorPalette::PrimaryMid]];}
#sidebarOptions .sliderPanel a:active {color:[[ColorPalette::PrimaryMid]]; background:[[ColorPalette::Background]];}
.wizard {background:[[ColorPalette::PrimaryPale]]; border:1px solid [[ColorPalette::PrimaryMid]];}
.wizard h1 {color:[[ColorPalette::PrimaryDark]]; border:none;}
.wizard h2 {color:[[ColorPalette::Foreground]]; border:none;}
.wizardStep {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];
border:1px solid [[ColorPalette::PrimaryMid]];}
.wizardStep.wizardStepDone {background:[[ColorPalette::TertiaryLight]];}
.wizardFooter {background:[[ColorPalette::PrimaryPale]];}
.wizardFooter .status {background:[[ColorPalette::PrimaryDark]]; color:[[ColorPalette::Background]];}
.wizard .button {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::SecondaryLight]]; border: 1px solid;
border-color:[[ColorPalette::SecondaryPale]] [[ColorPalette::SecondaryDark]] [[ColorPalette::SecondaryDark]] [[ColorPalette::SecondaryPale]];}
.wizard .button:hover {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::Background]];}
.wizard .button:active {color:[[ColorPalette::Background]]; background:[[ColorPalette::Foreground]]; border: 1px solid;
border-color:[[ColorPalette::PrimaryDark]] [[ColorPalette::PrimaryPale]] [[ColorPalette::PrimaryPale]] [[ColorPalette::PrimaryDark]];}
#messageArea {border:1px solid [[ColorPalette::SecondaryMid]]; background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]];}
#messageArea .button {color:[[ColorPalette::PrimaryMid]]; background:[[ColorPalette::SecondaryPale]]; border:none;}
.popupTiddler {background:[[ColorPalette::TertiaryPale]]; border:2px solid [[ColorPalette::TertiaryMid]];}
.popup {background:[[ColorPalette::TertiaryPale]]; color:[[ColorPalette::TertiaryDark]]; border-left:1px solid [[ColorPalette::TertiaryMid]]; border-top:1px solid [[ColorPalette::TertiaryMid]]; border-right:2px solid [[ColorPalette::TertiaryDark]]; border-bottom:2px solid [[ColorPalette::TertiaryDark]];}
.popup hr {color:[[ColorPalette::PrimaryDark]]; background:[[ColorPalette::PrimaryDark]]; border-bottom:1px;}
.popup li.disabled {color:[[ColorPalette::TertiaryMid]];}
.popup li a, .popup li a:visited {color:[[ColorPalette::Foreground]]; border: none;}
.popup li a:hover {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; border: none;}
.popup li a:active {background:[[ColorPalette::SecondaryPale]]; color:[[ColorPalette::Foreground]]; border: none;}
.popupHighlight {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}
.listBreak div {border-bottom:1px solid [[ColorPalette::TertiaryDark]];}
.tiddler .defaultCommand {font-weight:bold;}
.shadow .title {color:[[ColorPalette::TertiaryDark]];}
.title {color:[[ColorPalette::SecondaryDark]];}
.subtitle {color:[[ColorPalette::TertiaryDark]];}
.toolbar {color:[[ColorPalette::PrimaryMid]];}
.toolbar a {color:[[ColorPalette::TertiaryLight]];}
.selected .toolbar a {color:[[ColorPalette::TertiaryMid]];}
.selected .toolbar a:hover {color:[[ColorPalette::Foreground]];}
.tagging, .tagged {border:1px solid [[ColorPalette::TertiaryPale]]; background-color:[[ColorPalette::TertiaryPale]];}
.selected .tagging, .selected .tagged {background-color:[[ColorPalette::TertiaryLight]]; border:1px solid [[ColorPalette::TertiaryMid]];}
.tagging .listTitle, .tagged .listTitle {color:[[ColorPalette::PrimaryDark]];}
.tagging .button, .tagged .button {border:none;}
.footer {color:[[ColorPalette::TertiaryLight]];}
.selected .footer {color:[[ColorPalette::TertiaryMid]];}
.sparkline {background:[[ColorPalette::PrimaryPale]]; border:0;}
.sparktick {background:[[ColorPalette::PrimaryDark]];}
.error, .errorButton {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::Error]];}
.warning {color:[[ColorPalette::Foreground]]; background:[[ColorPalette::SecondaryPale]];}
.lowlight {background:[[ColorPalette::TertiaryLight]];}
.zoomer {background:none; color:[[ColorPalette::TertiaryMid]]; border:3px solid [[ColorPalette::TertiaryMid]];}
.imageLink, #displayArea .imageLink {background:transparent;}
.annotation {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; border:2px solid [[ColorPalette::SecondaryMid]];}
.viewer .listTitle {list-style-type:none; margin-left:-2em;}
.viewer .button {border:1px solid [[ColorPalette::SecondaryMid]];}
.viewer blockquote {border-left:3px solid [[ColorPalette::TertiaryDark]];}
.viewer table, table.twtable {border:2px solid [[ColorPalette::TertiaryDark]];}
.viewer th, .viewer thead td, .twtable th, .twtable thead td {background:[[ColorPalette::SecondaryMid]]; border:1px solid [[ColorPalette::TertiaryDark]]; color:[[ColorPalette::Background]];}
.viewer td, .viewer tr, .twtable td, .twtable tr {border:1px solid [[ColorPalette::TertiaryDark]];}
.viewer pre {border:1px solid [[ColorPalette::SecondaryLight]]; background:[[ColorPalette::SecondaryPale]];}
.viewer code {color:[[ColorPalette::SecondaryDark]];}
.viewer hr {border:0; border-top:dashed 1px [[ColorPalette::TertiaryDark]]; color:[[ColorPalette::TertiaryDark]];}
.highlight, .marked {background:[[ColorPalette::SecondaryLight]];}
.editor input {border:1px solid [[ColorPalette::PrimaryMid]];}
.editor textarea {border:1px solid [[ColorPalette::PrimaryMid]]; width:100%;}
.editorFooter {color:[[ColorPalette::TertiaryMid]];}
#backstageArea {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::TertiaryMid]];}
#backstageArea a {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::Background]]; border:none;}
#backstageArea a:hover {background:[[ColorPalette::SecondaryLight]]; color:[[ColorPalette::Foreground]]; }
#backstageArea a.backstageSelTab {background:[[ColorPalette::Background]]; color:[[ColorPalette::Foreground]];}
#backstageButton a {background:none; color:[[ColorPalette::Background]]; border:none;}
#backstageButton a:hover {background:[[ColorPalette::Foreground]]; color:[[ColorPalette::Background]]; border:none;}
#backstagePanel {background:[[ColorPalette::Background]]; border-color: [[ColorPalette::Background]] [[ColorPalette::TertiaryDark]] [[ColorPalette::TertiaryDark]] [[ColorPalette::TertiaryDark]];}
.backstagePanelFooter .button {border:none; color:[[ColorPalette::Background]];}
.backstagePanelFooter .button:hover {color:[[ColorPalette::Foreground]];}
#backstageCloak {background:[[ColorPalette::Foreground]]; opacity:0.6; filter:'alpha(opacity:60)';}
/*}}}*/
/*{{{*/
* html .tiddler {height:1%;}
body {font-size:.75em; font-family:arial,helvetica; margin:0; padding:0;}
h1,h2,h3,h4,h5,h6 {font-weight:bold; text-decoration:none;}
h1,h2,h3 {padding-bottom:1px; margin-top:1.2em;margin-bottom:0.3em;}
h4,h5,h6 {margin-top:1em;}
h1 {font-size:1.35em;}
h2 {font-size:1.25em;}
h3 {font-size:1.1em;}
h4 {font-size:1em;}
h5 {font-size:.9em;}
hr {height:1px;}
a {text-decoration:none;}
dt {font-weight:bold;}
ol {list-style-type:decimal;}
ol ol {list-style-type:lower-alpha;}
ol ol ol {list-style-type:lower-roman;}
ol ol ol ol {list-style-type:decimal;}
ol ol ol ol ol {list-style-type:lower-alpha;}
ol ol ol ol ol ol {list-style-type:lower-roman;}
ol ol ol ol ol ol ol {list-style-type:decimal;}
.txtOptionInput {width:11em;}
#contentWrapper .chkOptionInput {border:0;}
.externalLink {text-decoration:underline;}
.indent {margin-left:3em;}
.outdent {margin-left:3em; text-indent:-3em;}
code.escaped {white-space:nowrap;}
.tiddlyLinkExisting {font-weight:bold;}
.tiddlyLinkNonExisting {font-style:italic;}
/* the 'a' is required for IE, otherwise it renders the whole tiddler in bold */
a.tiddlyLinkNonExisting.shadow {font-weight:bold;}
#mainMenu .tiddlyLinkExisting,
#mainMenu .tiddlyLinkNonExisting,
#sidebarTabs .tiddlyLinkNonExisting {font-weight:normal; font-style:normal;}
#sidebarTabs .tiddlyLinkExisting {font-weight:bold; font-style:normal;}
.header {position:relative;}
.header a:hover {background:transparent;}
.headerShadow {position:relative; padding:4.5em 0em 1em 1em; left:-1px; top:-1px;}
.headerForeground {position:absolute; padding:4.5em 0em 1em 1em; left:0px; top:0px;}
.siteTitle {font-size:3em;}
.siteSubtitle {font-size:1.2em;}
#mainMenu {position:absolute; left:0; width:10em; text-align:right; line-height:1.6em; padding:1.5em 0.5em 0.5em 0.5em; font-size:1.1em;}
#sidebar {position:absolute; right:3px; width:16em; font-size:.9em;}
#sidebarOptions {padding-top:0.3em;}
#sidebarOptions a {margin:0em 0.2em; padding:0.2em 0.3em; display:block;}
#sidebarOptions input {margin:0.4em 0.5em;}
#sidebarOptions .sliderPanel {margin-left:1em; padding:0.5em; font-size:.85em;}
#sidebarOptions .sliderPanel a {font-weight:bold; display:inline; padding:0;}
#sidebarOptions .sliderPanel input {margin:0 0 .3em 0;}
#sidebarTabs .tabContents {width:15em; overflow:hidden;}
.wizard {padding:0.1em 1em 0em 2em;}
.wizard h1 {font-size:2em; font-weight:bold; background:none; padding:0em 0em 0em 0em; margin:0.4em 0em 0.2em 0em;}
.wizard h2 {font-size:1.2em; font-weight:bold; background:none; padding:0em 0em 0em 0em; margin:0.4em 0em 0.2em 0em;}
.wizardStep {padding:1em 1em 1em 1em;}
.wizard .button {margin:0.5em 0em 0em 0em; font-size:1.2em;}
.wizardFooter {padding:0.8em 0.4em 0.8em 0em;}
.wizardFooter .status {padding:0em 0.4em 0em 0.4em; margin-left:1em;}
.wizard .button {padding:0.1em 0.2em 0.1em 0.2em;}
#messageArea {position:fixed; top:2em; right:0em; margin:0.5em; padding:0.5em; z-index:2000; _position:absolute;}
.messageToolbar {display:block; text-align:right; padding:0.2em 0.2em 0.2em 0.2em;}
#messageArea a {text-decoration:underline;}
.tiddlerPopupButton {padding:0.2em 0.2em 0.2em 0.2em;}
.popupTiddler {position: absolute; z-index:300; padding:1em 1em 1em 1em; margin:0;}
.popup {position:absolute; z-index:300; font-size:.9em; padding:0; list-style:none; margin:0;}
.popup .popupMessage {padding:0.4em;}
.popup hr {display:block; height:1px; width:auto; padding:0; margin:0.2em 0em;}
.popup li.disabled {padding:0.4em;}
.popup li a {display:block; padding:0.4em; font-weight:normal; cursor:pointer;}
.listBreak {font-size:1px; line-height:1px;}
.listBreak div {margin:2px 0;}
.tabset {padding:1em 0em 0em 0.5em;}
.tab {margin:0em 0em 0em 0.25em; padding:2px;}
.tabContents {padding:0.5em;}
.tabContents ul, .tabContents ol {margin:0; padding:0;}
.txtMainTab .tabContents li {list-style:none;}
.tabContents li.listLink { margin-left:.75em;}
#contentWrapper {display:block;}
#splashScreen {display:none;}
#displayArea {margin:1em 17em 0em 14em;}
.toolbar {text-align:right; font-size:.9em;}
.tiddler {padding:1em 1em 0em 1em;}
.missing .viewer,.missing .title {font-style:italic;}
.title {font-size:1.6em; font-weight:bold;}
.missing .subtitle {display:none;}
.subtitle {font-size:1.1em;}
.tiddler .button {padding:0.2em 0.4em;}
.tagging {margin:0.5em 0.5em 0.5em 0; float:left; display:none;}
.isTag .tagging {display:block;}
.tagged {margin:0.5em; float:right;}
.tagging, .tagged {font-size:0.9em; padding:0.25em;}
.tagging ul, .tagged ul {list-style:none; margin:0.25em; padding:0;}
.tagClear {clear:both;}
.footer {font-size:.9em;}
.footer li {display:inline;}
.annotation {padding:0.5em; margin:0.5em;}
* html .viewer pre {width:99%; padding:0 0 1em 0;}
.viewer {line-height:1.4em; padding-top:0.5em;}
.viewer .button {margin:0em 0.25em; padding:0em 0.25em;}
.viewer blockquote {line-height:1.5em; padding-left:0.8em;margin-left:2.5em;}
.viewer ul, .viewer ol {margin-left:0.5em; padding-left:1.5em;}
.viewer table, table.twtable {border-collapse:collapse; margin:0.8em 1.0em;}
.viewer th, .viewer td, .viewer tr,.viewer caption,.twtable th, .twtable td, .twtable tr,.twtable caption {padding:3px;}
table.listView {font-size:0.85em; margin:0.8em 1.0em;}
table.listView th, table.listView td, table.listView tr {padding:0px 3px 0px 3px;}
.viewer pre {padding:0.5em; margin-left:0.5em; font-size:1.2em; line-height:1.4em; overflow:auto;}
.viewer code {font-size:1.2em; line-height:1.4em;}
.editor {font-size:1.1em;}
.editor input, .editor textarea {display:block; width:100%; font:inherit;}
.editorFooter {padding:0.25em 0em; font-size:.9em;}
.editorFooter .button {padding-top:0px; padding-bottom:0px;}
.fieldsetFix {border:0; padding:0; margin:1px 0px 1px 0px;}
.sparkline {line-height:1em;}
.sparktick {outline:0;}
.zoomer {font-size:1.1em; position:absolute; overflow:hidden;}
.zoomer div {padding:1em;}
* html #backstage {width:99%;}
* html #backstageArea {width:99%;}
#backstageArea {display:none; position:relative; overflow: hidden; z-index:150; padding:0.3em 0.5em 0.3em 0.5em;}
#backstageToolbar {position:relative;}
#backstageArea a {font-weight:bold; margin-left:0.5em; padding:0.3em 0.5em 0.3em 0.5em;}
#backstageButton {display:none; position:absolute; z-index:175; top:0em; right:0em;}
#backstageButton a {padding:0.1em 0.4em 0.1em 0.4em; margin:0.1em 0.1em 0.1em 0.1em;}
#backstage {position:relative; width:100%; z-index:50;}
#backstagePanel {display:none; z-index:100; position:absolute; margin:0em 3em 0em 3em; padding:1em 1em 1em 1em;}
.backstagePanelFooter {padding-top:0.2em; float:right;}
.backstagePanelFooter a {padding:0.2em 0.4em 0.2em 0.4em;}
#backstageCloak {display:none; z-index:20; position:absolute; width:100%; height:100px;}
.whenBackstage {display:none;}
.backstageVisible .whenBackstage {display:block;}
/*}}}*/
/***
StyleSheet for use when a translation requires any css style changes.
This StyleSheet can be used directly by languages such as Chinese, Japanese and Korean which use a logographic writing system and need larger font sizes.
***/
/*{{{*/
body {font-size:0.8em;}
#sidebarOptions {font-size:1.05em;}
#sidebarOptions a {font-style:normal;}
#sidebarOptions .sliderPanel {font-size:0.95em;}
.subtitle {font-size:0.8em;}
.viewer table.listView {font-size:0.95em;}
.htmlarea .toolbarHA table {border:1px solid ButtonFace; margin:0em 0em;}
/*}}}*/
/*{{{*/
@media print {
#mainMenu, #sidebar, #messageArea, .toolbar, #backstageButton, #backstageArea {display: none ! important;}
#displayArea {margin: 1em 1em 0em 1em;}
/* Fixes a feature in Firefox 1.5.0.2 where print preview displays the noscript content */
noscript {display:none;}
}
/*}}}*/
<!--{{{-->
<div class='header' macro='gradient vert [[ColorPalette::PrimaryLight]] [[ColorPalette::PrimaryMid]]'>
<div class='headerShadow'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
<div class='headerForeground'>
<span class='siteTitle' refresh='content' tiddler='SiteTitle'></span>
<span class='siteSubtitle' refresh='content' tiddler='SiteSubtitle'></span>
</div>
</div>
<div id='mainMenu' refresh='content' tiddler='MainMenu'></div>
<div id='sidebar'>
<div id='sidebarOptions' refresh='content' tiddler='SideBarOptions'></div>
<div id='sidebarTabs' refresh='content' force='true' tiddler='SideBarTabs'></div>
</div>
<div id='displayArea'>
<div id='messageArea'></div>
<div id='tiddlerDisplay'></div>
</div>
<!--}}}-->
<!--{{{-->
<div class='toolbar' macro='toolbar closeTiddler closeOthers +editTiddler > fields syncing permalink references jump'></div>
<div class='title' macro='view title'></div>
<div class='subtitle'><span macro='view modifier link'></span>, <span macro='view modified date'></span> (<span macro='message views.wikified.createdPrompt'></span> <span macro='view created date'></span>)</div>
<div class='tagging' macro='tagging'></div>
<div class='tagged' macro='tags'></div>
<div class='viewer' macro='view text wikified'></div>
<div class='tagClear'></div>
<!--}}}-->
<!--{{{-->
<div class='toolbar' macro='toolbar +saveTiddler -cancelTiddler deleteTiddler'></div>
<div class='title' macro='view title'></div>
<div class='editor' macro='edit title'></div>
<div macro='annotations'></div>
<div class='editor' macro='edit text'></div>
<div class='editor' macro='edit tags'></div><div class='editorFooter'><span macro='message views.editor.tagPrompt'></span><span macro='tagChooser'></span></div>
<!--}}}-->
To get started with this blank TiddlyWiki, you'll need to modify the following tiddlers:
* SiteTitle & SiteSubtitle: The title and subtitle of the site, as shown above (after saving, they will also appear in the browser title bar)
* MainMenu: The menu (usually on the left)
* DefaultTiddlers: Contains the names of the tiddlers that you want to appear when the TiddlyWiki is opened
You'll also need to enter your username for signing your edits: <<option txtUserName>>
These InterfaceOptions for customising TiddlyWiki are saved in your browser
Your username for signing your edits. Write it as a WikiWord (eg JoeBloggs)
<<option txtUserName>>
<<option chkSaveBackups>> SaveBackups
<<option chkAutoSave>> AutoSave
<<option chkRegExpSearch>> RegExpSearch
<<option chkCaseSensitiveSearch>> CaseSensitiveSearch
<<option chkAnimate>> EnableAnimations
----
Also see AdvancedOptions
The final grade will be computing as follows:
25% Lab activity
75% Written paper (exam)
Remarks:
1. Final grade will be computed only if both grades are greater than 5
2. Lab grade will be computed only if all the lab assignments have been delivered
3. Seminar activity will be taken into account for final grade
Laboratory Work no. 1
Statement: Considering a small programming language (that we shall call mini-langauge), you have to write a scanner (lexical analyzer). The assignment can be divided in two parts:
1. Minilanguage Specification
The minilanguage should be a restricted form of a known programming language, and should contain the following:
- 2 simple data types and a user-defined type
- statements:
- assignment
- input/output
- conditional
- loop
- some conditions will be imposed on the way the identifiers and constants can be formed.
2. Scanner implementation
The scanner input will be a text file containind the source program, and will produce as output the following:
- PIF - Program Internal Form
- ST - Symbol Table
In addition, the program should be able to determine the lexical errors, specifying the location, and, if possible, the type of the error.
The scanner assignment will be diferentiated based on:
1. Identifiers:
a. length at most 8 characters
b. arbitrary length, no more than 250 characters
2. Symbol Table:
a. unique for identifiers and constants
b. separate tables for indentifiers, respectively
constants
3. Symbol Table Organization:
a. lexicographically sorted table
b. lexicographically binary tree
c. hashing table
Documenting the scanner program is COMPULSORY!
IMPORTANT:
Each week delay will be penalized with one point, and delays more than 2 weeks are NOT ACCEPTED!
Laboratory work is taken into consideration at the final mark, and acceptance at the final exam is conditioned by the delivery of all laboratory work.
Example:
Language Specification:
1 .Language Definition:
1.1 Alphabet:
1.1.a. Upper (A-Z) and lower case letters (a-z) of the English alphabet
b. Underline character '_';
c. Decimal digits (0-9);
Lexic:
a.Special symbols, representing:
- operators + - * / := < <= = >=
- separators [ ] { } : ; space
- reserved words:
array char const do else if int of program read
then var while write
b.identifiers
-a sequence of letters and digits, such that the first charater is a letter; the rule is:
identifier ::= letter | letter{letter}{digit}
letter ::= "A" | "B" | . ..| "Z"
digit ::= "0" | "1" |...| "9"
c.constants
1.integer - rule:
noconst:=+no|-no|no
no:=digit{no}
2.character
character:='letter'|'digit'
3.string
constchar:="string"
string:=char{string}
char:=letter|digit
2.2 Syntax:
The words - predefined tokens are specified between " and ":
a) Sintactical rules:
program ::= "VAR" decllist ";" cmpdstmt "."
decllist ::= declaration | declaration ";" decllist
declaration ::= IDENTIFIER ":" type
type1 ::= "BOOLEAN" | "CHAR" | "INTEGER" | "REAL"
arraydecl ::= "ARRAY" "[" nr "]" "OF" type1
type ::= type1|arraydecl
cmpdstmt ::= "BEGIN" stmtlist "END"
stmtlist ::= stmt | stmt ";" stmtlist
stmt ::= simplstmt | structstmt
simplstmt ::= assignstmt | iostmt
assignstmt ::= IDENTIFIER ":=" expression
expression ::= expression "+" term | term
term ::= term "*" factor | factor
factor ::= "(" expression ")" | IDENTIFIER
iostmt ::= "READ" | "WRITE" "(" IDENTIFIER ")"
structstmt ::= cmpdstmt | ifstmt | whilestmt
ifstmt ::= "IF" condition "THEN" stmt ["ELSE" stmt]
whilestmt ::= "WHILE" condition "DO" stmt
condition ::= expression RELATION expression
b) lexical rules:
IDENTIFIER ::= letter | letter{letter}{digit}
letter ::= "A" | "B" | . ..| "Z"
digit ::= "0" | "1" |...| "9"
RELATION ::= "<" | "<=" | "=" | "<>" | ">=" | ">"
The tokens are codified according to the following table:
- identifiers - code 0
- constants - code 1
- reserved words: each word has its own code
- operators: each operator has its own code
- separators: each separator has its own code
Codification:
-------------------------
| Token type | code |
-------------------------
| identifier | 0 |
-------------------------
| constant | 1 |
-------------------------
| program | 2 |
-------------------------
| array | 3 |
-------------------------
| of | 4 |
-------------------------
| var | 5 |
-------------------------
| integer | 6 |
-------------------------
| real | 7 |
-------------------------
| boolean | 8 |
-------------------------
| begin | 9 |
-------------------------
| end | 10 |
-------------------------
|read | 11 |
-------------------------
|write | 12 |
-------------------------
| for | 13 |
-------------------------
| to | 14 |
-------------------------
| do | 15 |
-------------------------
| if | 16 |
-------------------------
| then | 17 |
-------------------------
| else | 18 |
-------------------------
| and | 19 |
-------------------------
| or | 20 |
-------------------------
| not | 21 |
-------------------------
| : | 22 |
-------------------------
| ; | 23 |
-------------------------
| , | 24 |
-------------------------
| . | 25 |
-------------------------
| + | 26 |
-------------------------
| * | 27 |
-------------------------
| ( | 28 |
-------------------------
| ) | 29 |
-------------------------
| [ | 30 |
-------------------------
| ] | 31 |
-------------------------
| - | 32 |
-------------------------
| < | 33 |
-------------------------
| > | 34 |
-------------------------
| = | 35 |
-------------------------
| := | 36 |
-------------------------
... (documentation for the scanner application
Laboratory work 2
Regular grammars and finite automata
Write a program that:
1. Reads a grammar (from keyboard and from file)
2. Displays the elements of a grammar, using a menu: set of non-terminals, set of terminals, set of productions, the productions of a given non-terminal symbol
3. Verifies if the grammar is regular
4. Reads the elements of a FA (from keyboard and from file)
5. Displays the elements of a finite automata, using a menu: the set of states, the alphabet, all the transitions, the set of final state.
6. Given a regular grammar constructs the corresponding finite automaton.
7. Given a finite automaton constructs the corresponding regular grammar.
Laboratory 3
Context-free grammars
Task:
Starting from syntax rules in BNF notation from Lab 1, construct the context free grammar corresponding to your minilanguage to be used in parsing.
Deadline: 2 weeks
Lab Assignment no. 4- Parsing
One assignment for a team of 2 students!
One of the following parsing methods will be chosen:
1.a. recursive descendent
1.b. ll(1)
1.c. lr(0)
1.d. lr(1)
The representation of the parsing tree will be:
2.a. table (using father and sibling relation)
2.b. productions string
2.c. derivations string
The assignment is divided in the following phases:
STEP 1: perform the parsing of an input sequence
Input: - a context free grammar (the example from course)
- an input sequence
Output: the parsing tree corresponding to the input sequence or a message in case the sequence is not accepted.
Remark: Verify if the parsing method can be applied
STEP 2: performs the parsing for a program written in your language (lab. 1)
Input: PIF + minilanguage grammar
Output: parsing tree corresponding to the program or a message for errors (error diagnose where it is the case)
If the grammar does not satisfy the conditions of the parsing algorithm, consult your teacher!
Laboratory Assignment 5: Use of LEX and YACC
You may use any version (LEX or FLEX)
1) Write a LEX specification containing the regular expressions corresponding to your language specification.
2) Use Lex in order to obtain a scanner. Test for the same input as
in lab 1.
You may use any parser generator (yacc-bison, LLgen or other)
3) Write a specification file containing the production rules corresponding to the language specification.
4) Then, use the parser generator, and test it on the input as in Lab 3.
[[Lab 1]]
[[Lab 2]]
[[Lab 3]]
[[Lab 4]]
[[Lab 5]]
Rules and Requirements for Laboratory
Rules:
1. We will NOT tolerate cheating. Please, don’t copy your laboratory work, do it yourself.
2. Laboratory hours are compulsory – so, attend lab every week;
3. Respect delivery dates for each lab assignment. Each delay will be penalized.
4. You will NOT be accepted at the written exam if you do not deliver all assignments.
Requirements:
1. You will receive an individual assignment, specified by the teacher.
2. Each laboratory assignment should be presented in the following way: program (source files) and documentation. Laboratory assignments will be presented personally, sending them as e-mails, or through collegues will not be accepted.
3. Programs may be written in any language (your choice).
4. Documentation can be presented on paper or as a text file and should contain:
• specification of the task;
• analysis and design (in large);
• implementation details: data structures used, basic procedures or classes;
• use details (input/output format a.s.o).
Staff in charge:
Simona Motogna
Adriana Guran
Vladiela Petrascu
/***
|''Name:''|LegacyStrikeThroughPlugin|
|''Description:''|Support for legacy (pre 2.1) strike through formatting|
|''Version:''|1.0.2|
|''Date:''|Jul 21, 2006|
|''Source:''|http://www.tiddlywiki.com/#LegacyStrikeThroughPlugin|
|''Author:''|MartinBudden (mjbudden (at) gmail (dot) com)|
|''License:''|[[BSD open source license]]|
|''CoreVersion:''|2.1.0|
***/
//{{{
// Ensure that the LegacyStrikeThrough Plugin is only installed once.
if(!version.extensions.LegacyStrikeThroughPlugin) {
version.extensions.LegacyStrikeThroughPlugin = {installed:true};
config.formatters.push(
{
name: "legacyStrikeByChar",
match: "==",
termRegExp: /(==)/mg,
element: "strike",
handler: config.formatterHelpers.createElementAndWikify
});
} //# end of "install only once"
//}}}
[[Syllabus]]
[[Grading]]
[[Lab Assignment]]
[[Lab Requirements]]
[[Lab Schedule]]
Formal Languages and Compiler Design
1. Course objectives
Grammars and languages; Chomsky hierarchy; regular grammars, finite automata and the equivalence between them; context-free grammars, push-down automata and their equivalence.
Compiler construction fundamentals: compiling phases, scanning, persing and code generation.
2. Course contents
I. Grammars, languages, automata
Regular grammars and languages. Finite automata.
Context free grammars and languages. Pushdown automata.
Special grammars - LR(k), LL(k)
II. Compilers
General problems of compiler construction
Lexical parsers
Syntactical analyzers - ascendant and descendant methods
3. Bibliography
1. A.V. AHO, D.J. ULLMAN - Principles of computer design, Addison-Wesley, 1978.
2. A.V. AHO, D.J. ULLMAN - The theory of parsing, translation and compiling, Prentice-Hall, Engl. Cliffs., N.J., 1972, 1973.
3. CSÖRNYEI ZOLTÁN, Bevezetés a fordítóprogramok elméletébe, I, II., ELTE, Budapest, 1996
4. CSÖRNYEI ZOLTÁN, Fordítási algoritmusok, Erdélyi Tankönyvtanács, Kolozsvár, 2000.
5. DEMETROVICS JÁNOS-DENEV, J.-PAVLOV, R., A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.
6. D. GRIES - Compiler construction for digital computers,, John Wiley, New York, 1971.
7. D. GRUNE, H.BAL,C.JACOBS, K. LANGENDOEN – Modern Copiler Design, John Wiley, 2000
8. G. MOLDOVAN, V. CIOBAN, M. LUPEA - Limbaje formale si automate. Culegere de probleme, Univ. Babes-Bolyai, Cluj-Napoca, 1996.,l http://math.ubbcluj.ro/~infodist/alf/INDEX.HTM
9. S. MOTOGNA – Metode de proiectare a compilatoarelor, Ed. Albastra, 2006
10. L.D. SERBANATI - Limbaje de programare si compilatoare, Ed. Academiei RSR, 1987.
4. Thematic of didactic activities per weeks
Course 1. What is a compiler, general structure and compilation phases [6,9]
Course 2. Scanning [9,7,10]
Course 3. Formal languages - Basic notions: language, grammar, Chomsky hierarchy [2]
Course 4. Regular Grammars (RG) and Finite Automata (FA). [2]
- Definitions
- Equivalence between RG and FA
Course 5. Regular expressions [2]
- Equivalence between regular languages, RG and FA;
- Closure properties;
- Pumping lemma
Course 6. Context-free grammars (CFG) [2]
- Definition, pumping lemma
- Syntax tree
- Equivalent transformations
Course 7. Push-down Automata (PDA)[2]
- Definition
- Equivalence to CFG
Course 8. Parsing [1,9]
- Basic notions. Representation of the syntax tree
- Classification of parsers
- Descending recursive parsing
Course 9. LL(1) Parsing [1,9,10]
- LL(k) grammars
- Functions FIRST and FOLLOW
- Constructing an LL(1) parser
Course 10. LR Parsing [1,9,10]
- Shift-reduce parsing
- Basic principles for LR(k) parsing; LR(k) grammars
- LR(0) canonical collection
Course 11. LR Parsing – cont. [1,9,10]
- Constructing an LR(0) parser
Course 12. LR Parsing – cont. [1,9,10]
- SLR parser
- LR(1) parser
- LALR parser
Course 13. Scanning and parsing generators [7,9]
- Scanning generator (lex)
- Parsing generators (yacc, lgen)
Course 14. Turing Machines[1]
5. Assessment
The final grade will reflect the seminar and lab activity and the knowledge obtained by the students.
The final mark will be compute from: 25% lab_mark + 75% exam_mark (including seminar work too).