text:
Parrot Virtual Machine/Parrot Grammar Engine

Parrot Grammar Engine
The Parrot Grammar Engine (PGE) is an implementation of Perl 6's regular expression syntax on Parrot. The Perl 6 regular expression syntax is much more powerful and expressive than the regular expression syntax in Perl 5. Since regular expression implementations in many other languages are based on the Perl 5 implementation, Perl 6 is more powerful than those too. The Perl 6 regular expression and grammar syntax is very similar to parser generators like the Perl 5 module "Parse::RecDescent", or the parser-generator programs Yacc and Bison. Unlike Yacc/Bison, however, the Perl 6 grammar engine uses a recursive descent algorithm instead of an LALR one. The differences are not important to the casual reader, but we will go into some more details about them later.

Perl 6 grammars are combinations of lexical analyzers (which break the source code into tokens) and parsers (which combine tokens into patterns). The lexical analysis portion of the grammar is the regular expression engine. The parser portion of the grammar engine is the rules system that we will describe here.

Parsers and Terminology
Before we talk about PGE any further, we need to discuss some more terminology, and we also need to take a quick look at the algorithms that parsers use. By understanding the algorithms and the limitations of those algorithms, you the compiler designer should be able to employ these tools more optimally.

Input to a compiler is a source code file, written in a particular high-level language, which consists of various components. Consider the following statement in the C programming language:

int x = add_both(5, 4);

This statement needs to be broken up into smaller chunks which represent the individual components. A chunk, as we have already seen, is called a "token". The regular expression engine, the lexical analyzer, is used to break the input into tokens by iteratively matching the input against known regular expressions. Using this method, the statement above can be broken down into the following tokens:

KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN "int"    "x"        "="   "add_both"  "("    "5"     ","      "4"    ")"

Notice that the whitespace has been removed from the list, so only the "important" stuff is turned into a token. Each token has two important pieces of information: The type ("KEYWORD", "IDENTIFIER", etc) and a value ("int", "x", etc). The parser can arrange the token types into a pattern, and the actions can use the token values to construct the PAST parse tree.

An ordered group of tokens is called a string if it matches a given input pattern for the parser. The set of all strings which are valid for a compiler is called the language. The rules that specify this language is called a grammar.

The third part of a compiler is the back end. The back end, also called the target code generator, turns the intermediate data representation of the input source (the parse tree) and converts it into the target language. In our case, the target language is PIR or PBC. All compilers are formed from these three key components: The lexical analyzer, the parser, and the back end. Parrot provides regular expressions for the lexical analyzer, and it handles all the target language generation. The only thing you, as a compiler designer, need to design is the parser. However, there is a lot of information about parsers that we need to know first.

There are two methods to parse a string of input tokens. First, we can do a top-down parse where we start with our highest-level token and try to find a match. Second, we can do a bottom-up parse where we start with the small tokens and try to combine them into bigger and bigger tokens until we have the highest-level. The ultimate goal of both parsing methods is to reduce the string of input tokens into a single match token.

Bottom-Up Parse
As a simple bottom-up parse example, we will start at the left side of our string of tokens and try to combine small tokens into bigger ones. What we want, in the end, is a token that represents the entire input. We do this by utilizing two fundamental operations: shift and reduce. A shift operation means we read a new input token into the parser. A reduce operation means we turn a matched pattern of small tokens into a single larger token. Let's put this method into practice below.

KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN "int"    "x"        "="   "add_both"  "("    "5"     ","      "4"    ")"

The above string turns into the string below if we realize that the tokens "int" and "x" are a variable declaration. We reduce the first two tokens into a variable declaration token:

DECLARATION OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN "="  "add_both"  "("    "5"     ","      "4"    ")"

Now, we move through the line, shifting tokens into the parser from left to right. We can't see anything that we can reduce until we reach the parenthesis. We can reduce the open and close parenthesis, and all the tokens in the middle of them into an argument list as shown below:

DECLARATION OPERATOR IDENTIFIER ARGUMENT_LIST "="  "add_both"

Now, we know that when we have an identifier followed by an argument list, that it is a function call. We reduce these two tokens to a single function call token:

DECLARATION OPERATOR FUNCTION_CALL "="

And finally, by skipping a few steps, we can convert this into an assignment statement:

ASSIGNMENT_STATEMENT

Every time we reduce a set of small tokens into a bigger token, we add them to the tree. We add the small tokens as children of the bigger token. This type of parser that we are talking about here is called a "shift-reduce" parser because those are the actions the parser performs. A subset of shift-reduce parsers that are useful for arithmetic expressions is called an operator precedence parser, and is one that we will talk about more below.

Top-Down Parse
A top-down parser is a little bit different from a bottom-up parser. We start with the highest level token, and we try to make a match by testing for smaller patterns. This process can be inherently inefficient, because we must often test many different patterns before we can find one that matches. However, we gain an ability to avoid shift-reduce conflicts and also gain a certain robustness because our parser is attempting multiple options before giving up. Let's say that we have a string of tokens, and a top-level definition for a STATEMENT token. Here is the definition in a format called a context-free grammar:

STATEMENT := ASSIGNMENT | FUNCTION_CALL | DECLARATION

This is a simple example, of course, and certainly not enough to satisfy a language like C. The ":=" symbol is analogous to the words "is made of". The vertical bar "|" is the same as saying "or". So, the statement above says "A statement is made of an assignment or a function call or a declaration".

We have this grammar rule that tells us what a statement is, and we have our string of input tokens:

KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN "int"    "x"        "="   "add_both"  "("    "5"     ","      "4"    ")"

The top-down parser will try each alternative in the STATEMENT definition to see if it matches. If one doesn't match, it moves to the next one and tries again. So, we try the ASSIGNMENT rule, and ASSIGNMENT is defined like this:

ASSIGNMENT := (VARIABLE_NAME | DECLARATION) '=' (EXPRESSION | FUNCTION_CALL)

Parenthesis are used to group things together. In English, this statement says "An assignment is a variable name or a declaration, followed by a '=' followed by an expression or a function call". So, to satisfy ASSIGNMENT, we try VARIABLE_NAME first, and then we try DECLARATION. The string "int x" is a declaration and not a simple variable name, so VARIABLE_NAME fails, and DECLARATION succeeds. Next, the '=' matches. To satisfy the last group, we try EXPRESSION first, which fails, and then we try FUNCTION_CALL, which succeeds. We proceed this way, trying alternatives and slowly moving down to smaller and smaller tokens, until we've matched the entire input string. Once we have matched the last input token, if we have also satisfied the top-level match, the parser succeeds.

This type of parser is called a "recursive descent" parser, because we recurse into each subrule, and slowly descend from the top of the parse tree to the bottom. Once the last subrule succeeds, the whole match succeeds and the parser returns.

In this process, when a rule matches, we create a node in our PAST tree. Because we test all subrules first before a rule succeeds, all the children nodes are created before the higher-level nodes are created. This creates the parse tree from the bottom going up, even though we started at the top of the tree and moved down.

Top-down parsers can be inefficient because the parser will attempt to match patterns that obviously cannot succeed. However, there are techniques that we can use to "prune" the tree of possibilities by directing the parser towards certain paths or stopping it from going down branches that will not match. We can also prevent the parser from backtracking from subrules back up to larger rules, which helps to reduce unnecessary repetition.

Rules And Actions
A recursive descent parser, like the one used in PGE, is a top-down parser. This means it attempts to start at the highest-level definition and work its way down to match the given input. The top-level rule is always called TOP. After that, we can create as many other rules as we need to in order to specify our entire grammar. Let's start by creating a very simple recursive descent parser to try and parse the input that we gave earlier:

int x = add_both(5, 4);

Here is part of our basic parser:

rule TOP { |  | }

rule assignment { '=' }

rule lvalue {  |  }

rule rvalue { |  }

rule function_call { '(' ')' }

rule variable_declaration { 'int' }

This is only part of the parser, but the idea should be clear. We define each rule in terms of constants or other rules. The angle brackets "<" and ">" indicate that we need to match a subrule. Single quotes are used to indicate something that is a literal string constant.

Basic Rules
Rules have a couple basic operators that we can use, some of which have already been discussed. People who are familiar with regular expressions will recognize most of them.

We have already discussed the or operator "|". Here are some examples.

Actions
As it successfully matches rules, PGE creates a special "match object", which contains information about the match. This match object can be sent to a function written in PIR or NQP for processing. The processing function that receives the match object is called the action. Each rule in the grammar has an associated action function with the same name.

When we have completed a successful match, we need to send the match object to the action method. We do this with the special symbol. sends the current match object, not necessarily the complete one. You can call  multiple times in a rule to invoke the action method multiple times, if needed. Here is an example:

rule k_r { {*}      #Calls the action method with an empty match object 'hello' {*}      #calls the action method after matching 'hello' 'world' {*}      #Calls the action method after matching 'hello' 'world' }

There are two important points to remember about action methods:

 * 1) The parser moves from left-to-right, top-to-bottom. In the k_r example above, if the input was "hello johnny", the action method would get called the first two times, but the rule would fail to match the word "world" and the action method would not be called the third time.
 * 2) The parser returns after a successful match, even if there are more possibilities to try. Consider this example below, where only one of the action methods can be called depending on the result of the alternation. In this example, if the input is "hello franky", the action method only gets called for the  after 'franky'. After that matches, the parser returns and does not try to match 'johnny'.

rule say_hello { 'hello' [    | 'tommy' {*} | 'franky' {*} | 'johnny' {*} ] }

It can be very helpful sometimes to specify which action method got called, when there is a list of possibilities. This is because we want to treat certain matches differently from others. to treat an action method differently, we use a special comment syntax:

rule say_hello { 'hello' [    | 'tommy' {*}  #= tommy | 'franky' {*} #= franky | 'johnny' {*} #= johnny ] }

The special "#=" symbol is not a regular comment. Instead, it's a second parameter for the action method called a "key". If you use "#=", the action method will receive two arguments: the match object and the key. You can then test the value of the key to determine how to treat the match object. We will discuss this more in the next chapter about NQP.

Resources

 * Synopsis 5: Regexes and Rules
 * Synopsis 6: Subroutines


text: Category:Book:Japan's Foreign Policy Toward Vietnam 1978-1992

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Category:Book:Korean History

ko:분류:한국의 역사

title: Category:Book:Korean History


text: Category:Book:Latin-American History

title: Category:Book:Latin-American History


text: Category:Book:Modern History

title: Category:Book:Modern History


text: Category:Book:The Rowers of Vanity Fair

title: Category:Book:The Rowers of Vanity Fair


text: Category:Book:Warfare

title: Category:Book:Warfare


text: User talk:64.218.187.134

title: User talk:64.218.187.134


text: Category:Wikibooks:History

title: Category:Wikibooks:History


text: Category:Book:Conhistory

title: Category:Book:Conhistory


text:
Parrot Virtual Machine/Building A Compiler

HLL Compilers
Now that we know NQP and PGE, we have the tools that we need to start writing a compiler for our favorite language. Let's review the steps to creating a compiler:

 * 1) Write Grammar using PGE
 * 2) Write Actions using NQP
 * 3) Actions create PAST tree
 * 4) PCT converts PAST into PIR
 * 5) Parrot converts PIR into bytecode.

After step 5, if we have done everything correctly, we should have a working compiler. Of course, there is a lot of work to do before we reach step 5. Lucky for us, however, steps 4 and 5 are automated by the build process, so we only need to worry about 1, 2, and 3. In the Tutorials section we are going to have several language-building tutorials that you can follow.

Creating a PAST Tree
PAST nodes are objects that your NQP Action methods must create. PCT automatically inserts these nodes into the tree once you create them. PAST nodes are complex objects with an array and a hash component. The array stores a list of references to the children nodes, and the hash stores information about the node itself. Creating the past tree means that we create nodes in lower-rules, and insert them into the array for higher rules. As we go, we set the necessary options for each rule, so that PCT can generate the appropriate code.

There is a reference for the various types of PAST nodes available in the appendix.

PAST::Node is the base class from which the other PAST node types are derived. The other types are PAST::Stmts, PAST::Val, PAST::Var, PAST::Op, and PAST::Block.

PAST::Op
 * PAST::Op nodes are operations that need to be performed.

PAST::Val
 * PAST::VAL nodes are constant values like integers or strings

PAST::Var
 * PAST::Var nodes are variables

PAST::Block
 * PAST::Block nodes are used for lexically scoping variables and defining subroutines. They keep other nodes together.

PAST::Stmts
 * PAST::Stmts nodes are just groups of other nodes, and perform no task besides basic organization.

Once you have created the necessary node, you insert it into the parse tree with the keyword.

The Match Object
The Match object is a special object that contains a hash. The match object hash contains information about the matched rule. Each element in the hash is named after one of the sub-rules in the rule. For instance, if we have the following rule:

rule sentence { }

Then the match rule would have entries "adjective", "noun", "adverb", and "verb". The value of the hash for each of these keys are the values that were returned from the subrules using the  command, if any. So, we would have the following fields:

$ $  $  $

We would then use the values of each of these to produce and  a node for the   rule. If each of these fields return PAST nodes of their own, we should push those

Examples
We are going to show some very small examples here to demonstrate the basic compiler construction method. More advanced tutorials are provided in the Tutorials section.


text:
Wikibooks talk:WikiProject History

Other wikibooks history
Seems to be already WikiProject_History, maybe redirect the page here and contact the member. ChessCreator (talk) 19:34, 8 April 2008 (UTC)
 * I hadn't seen that. It says it is obsolete, so I've linked it here. Thanks. Νεοπτόλεμος ( talk | email | contribs ) 19:52, 8 April 2008 (UTC)
 * History merged after the move and renamed WikiProject Chess for consistency. History should be about the history of Wikibooks. All wikiprojects should use Wikibooks:Wikiproject XXXXXXX as the format to avoid any such conflicts. – Mike.lifeguard  | talk 01:34, 9 April 2008 (UTC)
 * I strongly disagree that 'All wikiprojects should use Wikibooks:Wikiproject XXXXXXX as the format to avoid any such conflicts.' If you are concerned about the conflicts a better way is to redirect Wikibooks:Wikiproject XXXXXXX to whatever format is choosen. It's quite inappropriate to change existing wikibooks that have already been branded with a name, and known as that name from many links in wikibooks and elsewhere (like wikipedia). Also the practical problem of the name 'Wikibooks:Wikiproject XXXXXXX' being to long to sensible displayed in sidebars. ChessCreator (talk) 15:39, 9 April 2008 (UTC)

WB:HISTORY
Created shortcut to the Wikibooks History page. It's also a trick to highlight link on User box on project page. ChessCreator (talk) 21:43, 8 April 2008 (UTC)

United We Stand
Hello folks,

I am Geoff Plourde (Geo.plrd). my Wikiversity course (Introduction to US History) will be writing a US History textbook called United We Stand. We are using the AP and California Standards as references. If anyone wants to learn about US history, or write a textbook on the subject, feel free to help us out. Geo.plrd (talk) 05:57, 15 October 2008 (UTC)
 * Hmmm. Well, the name of the book appears POV to me. Anyway, as long as the book is of academic use the POV in the title isn't a big deal though :-)-Ravichandar My coffee shop 14:59, 13 November 2008 (UTC)

note
this page looks interesting. thanks. --Sm8900 (discuss • contribs) 12:16, 16 February 2020 (UTC)

title: Wikibooks talk:WikiProject History


text:
Windows Add-ons

This book is devoted to unofficial Microsoft Windows extensions and add-ons that provide core functionality that the operating system as a distribution lacks. Feel free to file a brief tutorial of your favorite Windows components.

Components that aren't wholly free are not welcome in this book. It is not intended as an advertisement for proprietary vendors; nor, is intended to document native Windows features.

Table of Contents

 * Image Manipulation
 * 1) ; Resize-O-Matic : This program makes resizing an image a simple right-mouse-click on the image or images.
 * 2) ; Image Resizer for Windows : This program works like the above but works on Windows 7.
 * 3) ; GIMP (Separate Wikibook)

title: Windows Add-ons


text:
Windows Add-ons/Image/Resize-O-Matic

Image Resizer for Windows is a replacement for Resize-O-Matic that works with Windows 7

Ever need to simply resize a mass of images with ease? Resize-O-Matic is a quick and convenient way to do that. It will add a new option to your context-menu.

Downloading

 * Download the program directly at at the source forge site
 * Or, browse to the SourceForge project for Resize-O-Matic → Select Download → Download the file ending in .exe.

Installing

 * 1) Double click the icon
 * 2) Click Next until you can no longer hit Next.
 * 3) Click Finish

Using

When Resize-o-matic resizes images, it does not by default replace the original copy. It just saves another copy under a new name. For instance, if you resize foo.jpg you will have a new file named foo (Small).jpg.
 * 1) Select image(s)
 * 2) Select desired size
 * 3) * For the purpose of the web you almost surely want 640x480.
 * 4) Click Ok

Advanced Usage
Resize-O-Matic also supports a few "advanced" options. They aren't really all that advaned.
 * 1) Custom resizing dimensions
 * 2) Make pictures smaller but not larger
 * 3) Resize the original pictures (don't create copies!).
 * 4) * This is probably the most useful feature.

title: Windows Add-ons/Image/Resize-O-Matic


text: Category:Book:History of Kosovo

title: Category:Book:History of Kosovo


text: Category:Book:World War II

title: Category:Book:World War II


text:
Talk:Telecommunications Theory/Flow - Presence - Transportation Theory

Wikipedia has a decent article on flow already and some of that should be used here.

Separate topics
Should these be broken up into separate topics?


text: Category:Book:Israeli History

title: Category:Book:Israeli History


text: User talk:75.90.52.172

title: User talk:75.90.52.172


text: User talk:125.17.147.68

title: User talk:125.17.147.68


text:
Category:Book:History of Christianity

Romans 2:12

title: Category:Book:History of Christianity


text: Category:Book:Film History

title: Category:Book:Film History


text:
Parrot Virtual Machine/Squaak Tutorial

This tutorial for the toy language "Squaak" was first presented on http://www.parrotblog.org. The tutorials have been released into the public domain by the author, and so have been adapted for use here on Wikibooks. The initial upload revisions for each of these pages are released into the public domain. Subsequent edits made to these pages are released under the GFDL.

File names used in these pages are relative to the Parrot source distribution. "PDD" are the Parrot Design Documents, a series of explanatory documents which are located in POD format in the Parrot repository, or on the http://www.parrot.org website. For more information about downloading the Parrot repository, see the chapter on Building Parrot.

These pages have been changed as necessary to fit Wikibooks, and are being improved like any other book or module. If you appreciate this tutorial and would like to leave comments for its original author, you can do so at http://www.parrotblog.org.

 * Notice:Since this tutorial has been released, a number of changes have been made to the underlying tools: PCT, PGE, and NQP. Because of this, the code discussed in the tutorial might not be accurate and will likely not operate correctly anymore. These pages will be updated eventually to reflect these changes, but they are not currently up to date.

title: Parrot Virtual Machine/Squaak Tutorial


text: Category:Book:History of Computers

title: Category:Book:History of Computers


text: Category:Book:Diplomatic History

title: Category:Book:Diplomatic History


text:
Parrot Virtual Machine/Squaak Tutorial/Introduction

Introduction
This is the first episode in a tutorial series on building a compiler with the Parrot Compiler Tools. If you're interested in virtual machines, you've probably heard of the Parrot virtual machine. Parrot is a generic virtual machine designed for dynamic languages. This is in contrast with the Java virtual machine (JVM) and Microsoft's Common Language Runtime (CLR), both of which were designed to run static languages. Both the JVM and Microsoft (through the Dynamic Language Runtime -- DLR) are adding support for dynamic languages, but their primary focus is still static languages.

High Level Languages
The main purpose of a virtual machine is to run programs. These programs are typically written in some High Level Language (HLL). Some well-known dynamic languages (sometimes referred to as scripting languages) are Lua, Perl, PHP, Python, Ruby, and Tcl. Parrot is designed to be able to run all these languages. Each language that Parrot hosts needs a compiler to parse the syntax of the language and generate Parrot instructions.

If you've never implemented a programming language (and maybe even if you have implemented a language), you might consider writing a compiler a bit of a black art. I know I did when I became interested. And you know what? It is. Compilers are complex programs, and implementing a language can be very difficult.

The Facts: 1) Parrot is suitable for running virtually any dynamic language known, but before doing so, compilers must be written, and 2) writing compilers is rather difficult.

The Parrot Compiler Toolkit
Enter the Parrot Compiler Toolkit (PCT). In order to make Parrot an interesting target for language developers, the process of constructing a compiler should be supported by the right tools. Just as any construction task becomes much easier if you have the right tools (you wouldn't build a house using only your bare hands, would you?), the same is true for constructing a compiler. The PCT was designed to do just that: provide powerful tools to make writing a compiler for Parrot childishly easy.

This tutorial will introduce the PCT by demonstrating the ease with which a (simple) language can be implemented for Parrot. The case study language is not as complex as a real-world language, but this tutorial is written to whet your appetite and show the power of the PCT. This tutorial will also present some exercises which you can explore in order to learn more details of the PCT not covered in this tutorial.

Squaak: A Simple Language
The case study language, named Squaak, that we will be implementing on Parrot will be a full-fledged compiler that can compile a program from source into Parrot Intermediate Representation (PIR) (or run the PIR immediately). It can also be used as a command-line interpreter. Squaak demonstrates some common language constructs, but at the same time is lacking some other, seemingly simple features. For instance, our language will not have return, break or continue statements (or equivalents in your favorite syntax).

Squaak will have the following features:

 * global and local variables
 * basic types: integer, floating-point and strings
 * aggregate types: arrays and hash tables
 * operators: +, -, /, *, %, <, <=, >, >=, ==, !=, .., and, or, not
 * subroutines and parameters
 * assignments and various control statements, such as "if" and "while"

As you can see, a number of common (more advanced) features are missing. Most notable are:

 * classes and objects
 * exceptional control statements such as break and return
 * advanced control statements such as switch
 * closures (nested subroutines and accessing local variables in an outer scope)

The Compiler Tools
The Parrot Compiler Tools we'll use to implement Squaak consist of the following parts:

 * Parrot Grammar Engine (PGE). The PGE is an advanced engine for regular expressions. Besides regexes as found in Perl 5, it can also be used to define language grammars, using Perl 6 syntax. (Check the references for the specification.)
 * Parrot Abstract Syntax Tree (PAST). The PAST nodes are a set of classes defining generic abstract syntax tree nodes that represent common language constructs.
 * HLLCompiler class. This class is the compiler driver for any PCT-based compiler.
 * Not Quite Perl (6) (NQP). NQP is a lightweight language inspired by Perl 6 and can be used to write the methods that must be executed during the parsing phase, just as you can write actions in a Yacc/Bison input file.

Getting Started
For this tutorial, it is assumed you have successfully compiled parrot (and maybe even run the test suite). If you browse through the languages directory in the Parrot source tree, you'll find a number of language implementations. Most of them are not complete yet; some are actively maintained actively and others aren't. If, after reading this tutorial, you feel like contributing to one of these languages, you can check out the mailing list or join IRC (see the references section for details).

The languages subdirectory is the right spot to put our language implementation. Parrot comes with a special Perl5 script to generate the necessary files for a language implementation. Before it can be run, parrot must be installed for development. From parrot's root directory, type:

$ make install-dev

In order to generate a new directory containing files for our language, type (assuming you're in parrot's root directory):

$ perl tools/dev/mk_language_shell.pl Squaak

(Note: if you're on Windows, you should use backslashes.) This will generate the files in a directory "squaak", and use the name "Squaak" as the language's name. After this, go to this directory and type:

$ parrot setup.pir test

This will compile the generated files and run the test suite. If you want more information on what files are being generated, please check out the references at the end of this episode.

Note that we didn't write a single line of code, and already we have the basic infrastructure in place to get us started. Of course, the generated compiler doesn't even look like the language we will be implementing, but that's ok for now. Later we'll adapt the grammar to accept our language.

Now you might want to actually run a simple script with this compiler. Launch your favorite editor, and put in this statement:

say "Squaak!";

Save the file (for instance as test.sq) and type:

$ parrot squaak.pbc test.sq

This will run Parrot, specifying squaak.pbc as the file to be run by Parrot, which takes a single argument: the file test.sq. If all went well, you should see the following output:

$ parrot squaak.pbc test.sq   Squaak!

Instead of running a script file, you can also run the Squaak compiler as an interactive interpreter. Run the Squaak compiler without specifying a script file, and type the same statement as you wrote in the file:

$ parrot squaak.pbc say "Squaak!";

which will print:

Squaak!

What's Next?
This first episode of this tutorial is mainly an overview of what will be coming. Hopefully you now have a global idea of what the Parrot Compiler Tools are, and how they can be used to build a compiler targeting Parrot. If you want to check out some serious usage of the PCT, check out Rakudo (Perl 6 on Parrot) or Pynie (Python on Parrot).

The next episodes will focus on the step-by-step implementation of our language, including the following topics:

 * structure of PCT-based compilers
 * using PGE rules to define the language grammar
 * implementing operator precedence using an operator precedence table
 * using NQP to write embedded parse actions
 * implementing language library routines

In the mean time, experiment for yourself. You are welcome to join us on IRC (see the References section for details). Any feedback on this tutorial is appreciated.

Exercises
The exercises are provided at the end of each episode of this tutorial. In order to keep the length of this tutorial somewhat acceptable, not everything can be discussed in full detail. The answers and/or solutions to these exercises will be posted several days after the episode.


text: Category:Book:COSTP World History Project


text: Category:Book:VCE History Revolutions

title: Category:Book:VCE History Revolutions


text:
Parrot Virtual Machine/Squaak Tutorial/Poking in Compiler Guts

In the first episode, we introduced the Parrot Compiler Tools, and generated a very simple language using a shell script provided with the Parrot distribution. We also announced Squaak, a simple programming language developed specially for this tutorial. Squaak will be the case study to show how PCT can be used as a very effective set of tools to implement a language for Parrot. A list of features of Squaak was specified. If you felt lucky, you might even have tried to do the exercise at the end of the previous episode.

In this episode, we will take a closer look at the generated compiler. We shall check out the different stages of the compilation process, and show what's going on in PCT-based compilers.

Under The Hood
Remember how we invoked our compiler in the previous episode? We can pass a file, or invoke the compiler without a command line argument, in which case our compiler enters the interactive mode. Consider the first case, passing the file test.sq, just as we did before:

$ parrot squaak.pbc test.sq

When invoking our compiler like this, the file test.sq is compiled and the generated code (bytecode) is executed immediately by Parrot. How does this work, you might wonder. The interpretation of a script is done through a series of transformations, starting at the script source and ending in a format that can be executed by Parrot. Compilers built with the PCT (based on the HLL::Compiler class) can take a target option, to show one of the intermediate representations. This option can have the following values, corresponding to the four default compilation phases of an HLLCompiler object:

 * --target=parse
 * --target=past
 * --target=post
 * --target=pir

This is an example of using the target option set to "parse", which will print the parse tree of the input to stdout:

$ parrot squaak.pbc --target=parse test.sq

In interactive mode, giving this input:

say 42;

will print this parse tree (without the line numbers):

1 "parse" => PMC 'Regex;Match' => "say 42;\n" @ 0 { 2    => PMC 'Regex;Match' => "say 42;\n" @ 0 { 3        => ResizablePMCArray (size:1) [ 4            PMC 'Regex;Match' => "say 42" @ 0 { 5                 => PMC 'Regex;Match' => "say 42" @ 0 { 6                     => ResizablePMCArray (size:1) [ 7                        PMC 'Regex;Match' => "42" @ 4 { 8                            => PMC 'Regex;Match' => "42" @ 4 { 9                                => PMC 'Regex;Match' => "42" @ 4 10                                 => \parse[0][0] 11                            }    12                         }    13                     ]    14                     => PMC 'Regex;Match' => "say" @ 0 15                }    16             }    17         ]    18     }    19 }

When changing the value of the target option, the output changes into a different representation of the input. Why don't you try that right now?

So, a HLL::Compiler object has four compilation phases: parsing, construction of a Parrot Abstract Syntax Tree (PAST), construction of a Parrot Opcode Syntax Tree (POST), generation of Parrot Intermediate Representation (PIR). After compilation, the generated PIR is executed immediately.

If your compiler needs additional stages, you can add them to your HLL::Compiler object. For Squaak, we will not need this, but for details, check out compilers/pct/src/PCT/HLLCompiler.pir.

We shall now discuss each compilation phase in more detail. The first two phases, parsing the input and construction of the PAST are executed simultaneously. Therefore, these are discussed together.

Parse phase: match objects and PAST construction
During the parsing phase, the input is analyzed using Perl 6's extended regular expressions, known as Rules (see Synopsis 5 for details). When a rule matches some input string, a so-called Match object is created. A Match object is a combined array and hashtable, implying it can be indexed by integers as well as strings. As rules typically consist of other (sub) rules, it is easy to retrieve a certain part of the match. For instance, this rule:

rule if_statement { 'if' 'then' 'end' {*}   }

has two other subrules: expression and statement. The match object for the rule if_statement represents the whole string from if to end. When you're interested only in the expression or statement part, you can retrieve that by indexing the match object by the name of the subrule (in this case, expression and statement, respectively).

During the parse phase, the PAST is constructed. There is a small set of PAST node types, for instance, PAST::Var to represent variables (identifiers, such as print), PAST::Val to represent literal values (for instance, "hello" and 42), and so on. Later we shall discuss the various PAST nodes in more detail.

Now, you might wonder, at which point exactly is this PAST construction happening? This is where the special {*} symbol comes in, just below the string 'if' in the if_statement rule shown above. These special markers indicate that a parse action should be invoked. Such a parse action is just a method that has the same name as the rule in which it is written (in this case: if_statement). So, during the parsing phase, several parse actions are executed, each of which builds a piece of the total PAST representing the input string. More on this will be explained later.

The Parrot Abstract Syntax Tree is just a different representation of the same input string (your program being compiled). It is a convenient data structure to transform into something different (such as executable Parrot code) but also to do all sorts of analysis, such as compile-time type checking.

PAST to POST
After the parse phase during which the PAST is constructed, the  transforms this PAST into something called a Parrot Opcode Syntax Tree (POST). The POST representation is also a tree structure, but these nodes are on a lower abstraction level. For instance, on the PAST level there is a node type to represent a  statement (constructed as   ). The template for a while statement typically consists of a number of labels and jump instructions. On the POST level, the same while statement is represented by a set of nodes, each representing a one instruction or a label. Therefore, it is much easier to transform a POST into something executable than when this is done from the PAST level.

Usually, as a user of the PCT, you don't need to know details of POST nodes, which is why this will not be discussed in further detail. Use the target option to see what a POST looks like.

POST to PIR
In the fourth (and final) stage, the POST is transformed into Parrot Intermediate Representation (PIR). As mentioned, transforming a POST into something executable is rather straightforward, as POST nodes already represent individual instructions and labels. Again, normal usage of the PCT does not require you to know any details about this transformation.

And now for the good news...
We established the general data flow of PCT-based compilers, which consists of four stages:

 * 1) source to parse tree
 * 2) parse tree to PAST
 * 3) PAST to POST
 * 4) POST to PIR

where we noted that the first two are done during the parse stage. Now, as you're reading this tutorial, you're probably interested in using the PCT for implementing Your Favorite Language for Parrot. We already saw that a language grammar is expressed in Perl 6 Rules. What about the other transformations?

Well, earlier in this episode we mentioned the term parse actions, and that these actions create PAST nodes. After you have written a parse action for each grammar rule, you're done!

Say what?
That's right. Once you have correctly constructed a PAST, your compiler can generate executable PIR, which means you just implemented your first language for Parrot. Of course, you still need to implement any language specific libraries, but that's besides the point.

PCT-based compilers already know how to transform a PAST into a POST, and how to transform a POST into PIR. These transformation stages are already provided by the PCT.

What's next?
In this episode we took a closer look at the internals of a PCT-based compiler. We discussed the four compilation stages, that transform an input string (a program, or script, depending on your definition) into a PAST, a POST and finally executable PIR. The next episodes is where the Fun Stuff is: we will be implementing Squaak for Parrot. Piece by piece, we will implement the parser and the parse actions. Finally, we shall demonstrate John Conway's "Game of Life" running on Parrot, implemented in Squaak.

Exercises
Starting in the next episode, the exercises will be more interesting. For now, it would be useful to browse around through the source files of the compiler, and see if you understand the relation between the grammar rules in Grammar.pg and the methods in Actions.pm.

It's also useful to experiment with the --target option described in this episode. If you don't know PIR, now is the time to do some preparation for that. There's sufficient information to be found on PIR, see the References section for details. In the mean time, if you have any suggestions, questions and whatnot, don't hesitate to leave a comment.


text: Category:Book:Knowledge Engineering for Historians


text:
Lojban/Pro-bridi

A word that functions as a pro-bridi is any word that temporarily has the same meaning as another bridi (such as a pro-sumti, or in English, a hypothetical "pro-verb").

Vocabulary
cei            assigns a a pro-bridi from the broda series to a bridi (equivalent to [goi]) broda          assigned pro-bridi (set meaning) #1 brode          assigned pro-bridi (set meaning) #2 brodi          assigned pro-bridi (set meaning) #3 brodo          assigned pro-bridi (set meaning) #4 brodu          assigned pro-bridi (set meaning) #5 da'o           cancels pro-assigns go'a           repeats a recent bridi (usually not the last 2 but may be the antepenultimate) go'e           repeats the next to last (penultimate) bridi go'i           preceding bridi; in answer to a yes/no question, repeats the claim, meaning "yes" go'ira'o       pro-bridi: preceding bridi; repeats claim as true, updates speaker/listener change true for me too go'o           repeats a future bridi, normally the next one go'u           repeats a remote past bridi mo             bridi/selbri/brivla question nei            repeats the current bridi no'a           repeats the bridi in which this one is embedded

Additional Notes and/or Examples

 * [cu] is not required when preceding a pro-selbri in the broda series.
 * Like [goi], [cei] does not always need to assign a pro-selbri of the broda series.
 * [lo tricu cu pu melbi cei mua mi .i lo nanmu mua mi] = The/a tree was beautiful/good-looking  to me.  The man was  to me.
 * In the immediately previous example, any occurrence of [mua] thereafter would mean [pu melbi], or "was good-looking". The pro-bridi keeps the same tense as the original selbri.
 * Pro-bridi not only reference the relation (selbri), and therefore the Lojbanic tense of the selbri, of a bridi; but all of the sumti as well. They do not, however, reference other participles (such as "xu", question/true-or-false...?).  They also reference the meaning of the bridi, not the precise words.
 * xu do prami mi
 * .i go'i (= .i mi prami do)

 * Do you love me?
 * repeat: last bridi meaning = (that-you = I) love (that-me = you) = Yes, I love you.

 * Iff not edited, a pro-bridi repeats the exact same sumti, tense, etc. as the bridi being referenced (though not other participles, as per immediately preceding and above). However, if sumti, tenses, etc. are specifically stated, then they replace the respective sumti, tenses, etc. of the referenced bridi.
 * [mi prami la dulsinei,as. --> .i la don kixoteis. (cu) pu go'i] = I love Dulcinea. --> Immediately previous bridi; with rewrite (edit) of first sumti (I --> Don Quixote), and of tense (unspecified --> past): Don Quixote loved Dulcinea. = I love Dulcinea. Don Quixote loved Dulcinea.

go'i Within and/or Near Quotations

 * These anaphoric words (basyvla) can be used in quotations, but never refer to any of the supporting text outside the quotation, since speakers presumably do not know that they may be quoted by someone else.

However, a "ri"-series or "go'a"-series reference within a quotation can refer to something mentioned in an earlier quotation if the two quotations are closely related in time and context. This allows a quotation to be broken up by narrative material without interfering with the pro-sumti within it (see example below). Of course, there is no problem with narrative material referring to something within a quotation: people who quote, unlike people who are quoted, are aware of what they are doing.
 * [la mark. cusku lu mi cliva le zdani li'u .i la .alksyndr. cusku lu mi go'i li'u] = Mark says, "I am leaving the house." Alexander (Alxinder) says, "Me too."

title: Lojban/Pro-bridi


text:
Parrot Virtual Machine/Squaak Tutorial/Squaak Details and First Steps

In the previous episodes we introduced the Parrot Compiler Tools (PCT). Starting from a high-level overview, we quickly created our own little scripting language called Squaak, using a Perl script provided with Parrot. We discussed the general structure of PCT-based compilers, and each of the default four transformation phases. This third episode is where the Fun begins. In this episode, we shall introduce the full specification of Squaak. In this and following episodes, we will implement this specification step by step, in small increments that are easy to digest. Once you get a feel for it, you'll notice implementing Squaak is almost trivial, and most important, a lot of fun! So, let's get started!

Squaak Grammar
Without further ado, here is the full grammar specification for Squaak. This specification uses the following meta-syntax:

statement  indicates a non-terminal, named "statement" {statement} indicates zero or more statements [step]     indicates an optional step 'do'       indicates the keyword 'do'

Below is Squaak's grammar. The start symbol is program.

program             ::= {stat-or-def}

stat-or-def         ::= statement | sub-definition

statement           ::= if-statement | while-statement | for-statement | try-statement | throw-statement | variable-declaration | assignment | sub-call | do-block

block               ::= {statement}

do-block            ::= 'do' block 'end'

if-statement        ::= 'if' expression 'then' block ['else' block] 'end'

while-statement     ::= 'while' expression 'do' block 'end'

for-statement       ::= 'for' for-init ',' expression [step] 'do' block 'end'

step                ::= ',' expression

for-init            ::= 'var' identifier '=' expression

try-statement       ::= 'try' block 'catch' identifier block 'end'

throw-statement     ::= 'throw' expression

sub-definition      ::= 'sub' identifier parameters block 'end'

parameters          ::= '(' [identifier {',' identifier}] ')'

variable-declaration ::= 'var' identifier ['=' expression]

assignment          ::= primary '=' expression

sub-call            ::= primary arguments

primary             ::= identifier postfix-expression*

postfix-expression  ::= key | index | member

key                 ::= '{' expression '}'

index               ::= '[' expression ']'

member              ::= '.' identifier

arguments           ::= '(' [expression {',' expression}] ')'

expression          ::= expression {binary-op expression} | unary-op expression | '(' expression ')' | term

term                ::= float-constant | integer-constant | string-constant | array-constructor | hash-constructor | primary

hash-constructor    ::= '{' [named-field {',' named-field}] '}'

named-field         ::= string-constant '=>' expression

array-constructor   ::= '[' [expression {',' expression} ] ']'

binary-op           ::= '+'  | '-'  | '/'  | '*'  | '%'  | '..' | 'and | 'or' | '>' | '>=' | '<'  | '<=' | '==' | '!='

unary-op            ::= 'not' | '-'

Gee, that's a lot, isn't it? Actually, this grammar is rather small compared to "real world" languages such as C, not to mention Perl 6. No worries though, we won't implement the whole thing at once, but in small steps. What's more, the exercises section contains enough exercises for you to learn to use the PCT yourself! The solutions to these exercises will be posted a few days later (but you really only need a couple of hours to figure them out).

Semantics
Most of the Squaak language is straightforward; the if-statement executes exactly as you would expect. When we discuss a grammar rule (for its implementation), a semantic specification will be included. This is to prevent myself from writing a complete language manual, which could take some pages.

Interactive Squaak
Although the Squaak compiler can be used in interactive mode, there is one point of attention to be noted. When defining a local variable using the 'var' keyword, this variable will be lost in any consecutive commands. The variable will only be available to other statements within the same command (a command is a set of statements before you press enter). This has to do with the code generation by the PCT, and will be fixed at a later point. For now, just remember it doesn't work.

Let's get started!
In the rest of this episode we will implement the basic parts of the grammar, such as the basic data types and assignments. At the end of this episode, you'll be able to assign simple values to (global) variables. It ain't much, but it's a very important first step. Once these basics are in place, you'll notice that adding a certain syntactic construct becomes a matter of minutes.

First, open your editor and open the files  and. The former implements the parser using Perl 6 rules, and the latter contains the parse actions, which are executed during the parsing stage.

In the file, you'll see the top-level rule, named "TOP". It's located at, ehm... the top. When the parser is invoked, it will start at this rule (a rule is nothing else than a method of the grammar class).

When we generated this language (in the first episode), some default rules were defined. Now we're going to make some small changes, just enough to get us started. Firstly, change the statement rule to this:

rule statement { {*}   }

and add these rules:

rule assignment { '='        {*}    }

rule primary { {*}   }

token identifier { <!keyword> {*}  }

token keyword { ['and'|'catch'|'do'  |'else' |'end' |'for' |'if' |'not'|'or'  |'sub'  |'throw'|'try' |'var'|'while']>> }

Now, change the rule "value" into this (renaming to "expression"):

rule expression { |  {*}       #= string_constant |  {*}      #= integer_constant }

Rename the rule "integer" as "integer_constant", and "quote" as "string_constant" (to better match our language specification).

Phew, that was a lot of information! Let's have a closer look at some things that may look unfamiliar. The first new thing is in the rule "identifier". Instead of the "rule" keyword, you see the keyword "token". In short, a token doesn't skip whitespace between the different parts specified in the token, while a rule does. For now, it's enough to remember to use a token if you want to match a string that doesn't contain any whitespace (such as literal constants and identifiers), and use a rule if your string does (and should) contain whitespace (such as a an if-statement). We shall use the word "rule" in a general sense, which could refer to a token. For more information on rules and tokens (and there's a third type, called "regex"), take a look at synopsis 5.

In token "identifier", the first subrule is called an assertion. It asserts that an "identifier" does not match the rule keyword. In other words, a keyword cannot be used as an identifier. The second subrule is called "ident", which is a built-in rule in the class PCT::Grammar, of which this grammar is a subclass.

In token "keyword", all keywords of Squaak are listed. At the end there's a ">>" marker, which indicates a word boundary. Without this marker, an identifier such as "forloop" would wrongly be disqualified, because the part "for" would match the rule keyword, and the part "loop" would match the rule "ident". However, as the assertion <!keyword> is false (as "for" could be matched), the string "forloop" cannot be matched as an identifier. The required presence of the word boundary prevents this.

The last rule is "expression". An expression is either a string-constant or an integer-constant. Either way, an action is executed. However, when the action is executed, it does not know what the parser matched; was it a string-constant, or an integer-constant? Of course, the match object can be checked, but consider the case where you have 10 alternatives, then doing 9 checks only to find out the last alternative was matched is somewhat inefficient (and adding new alternatives requires you to update this check). That's why you see the special comments starting with a " " character. Using this notation, you can specify a key, which will be passed as a second argument to the action method. As we will see, this allows us to write very simple and efficient action methods for rules such as expression. (Note there's a space between the  and the key's name).

Testing the Parser
It is useful to test the parser before writing any action methods. This can save you a lot of work; if you write the actions immediately after writing the grammar rules, and only later find out that your parser must be updated, then your action methods probably need to be updated as well. In Episode 2 we saw the target command line option. In order to test the parser, the "parse" target is especially helpful. When specifying this option, your compiler will print the parse tree of your input string, or print a syntax error. It is wise to test your parser with both correct and incorrect input, so you know for sure your parser doesn't accept input that it shouldn't.

And... Action!
Now we have implemented the initial version of the Squaak grammar, it's time to implement the parse actions we mentioned before. The actions are written in a file called. If you look at the methods in this file, here and there you'll see that the  object  , or rather, hash fields of it (like  ) is evaluated in scalar context, by writing " ".

As mentioned in Synopsis 5, evaluating a  object in scalar context returns its result object. Normally the result object is the matched portion of the source text, but the special  function can be used to set the result object to some other value.

This means that each node in the parse tree (a  object) can also hold its PAST representation. Thus we use the  function to set the PAST representation of the current node in the parse tree, and later use the   operator to retrieve the PAST representation from it.

In recap, the  object   and any subrules of it (for instance  ) represent the parse tree; of course,   represents only the parse tree what the rule matched. So, any action method has access to the parse tree that the equally named grammar rule matched, as the  object is always passed as an argument. Evaluating a parse tree in scalar context yields the PAST representation (obviously, this PAST object should be set using the  function).

If you're following this tutorial, I highly advise you to get your feet wet, and do the exercises. Remember, learning and not doing is not learning (or something like that :-). This week's exercises are not that difficult, and after doing them, you'll have implemented the first part of our little Squaak language.

What's next?
In this episode we introduced the full grammar of Squaak. We took the first steps to implement this language. The first, and currently only, statement type is assignments. We briefly touched on how to write the action methods that are invoked during the parsing phase. In the next episode, we shall take a closer look on the different PAST node types, and implement some more parts of the Squaak language. Once we have all basic parts in place, adding statement types will be rather straightforward. In the mean time, if you have any questions or are stuck, don't hesitate to leave a comment or contact me.

Exercises
This episode's exercises are simple enough to get started on implementing Squaak.

Some Notes
This means that the result object was not set properly (duh!). Make sure each action method is invoked (check each rule for a "{*}" marker), and that there is an action method for that rule, and that "make" is used to set the appropriate PAST node. Note that not all rules have action methods, for instance the "keyword" rule (there's no point in that).
 * Help! I get the error message "no result object".
 * While we're constructing parts of Squaak's grammar, we'll sometimes make a shortcut, by forgetting about certain rules for a while. For instance, you might have noticed we're ignoring float-constants right now. That's ok. When we'll need them, these rules will be added.


text:
Parrot Virtual Machine/Squaak Tutorial/PAST Nodes and More Statements

The previous episode introduced the full grammar specification of Squaak, and we finally started working on the implementation. If you're doing the exercises, you currently have basic assignments working; strings and integers can be assigned to (global) variables. This episode will focus on implementation of some statement types and explain a few bits about the different PAST node types.

Parrot Abstract Syntax Tree
A Parrot Abstract Syntax Tree (PAST) represents a program written in Squaak (or any other Parrot-ported language), and consists of nodes. In the previous episode, we already saw nodes to represent string and integer literals, identifiers and "operator" nodes, in our case assignment.

Other operators represent other high-level language constructs such as conditional statements, loops, and subroutine invocation. Depending on the node type, a PAST node can take child nodes. For instance, a PAST node to represent an if-statement can have up to three child nodes. The first child node represents the condition; if true, the second child node is evaluated. If the condition evaluates to false, and there's a third child node, this third child node is evaluated (the else part).

If the PAST represents a subroutine invocation, the child nodes are evaluated in a different way. In that case, the first child node represents the subroutine that is to be invoked (unless the  attribute was set on this node, but more on that in a later episode), and all other child nodes are passed to that subroutine as arguments.

It generally doesn't matter of which PAST node type the children are. For instance, consider a language in which a simple expression is a statement:

42

You might wonder what kind of code is generated for this. Well, it's really very simple: a new  node is created (of a certain type, for this example that would be ' '), and the value is assigned to this node. It might seem a bit confusing to write something like this, as it doesn't really do anything (note that this is not valid Squaak input):

if 42 then "hi" else "bye" end

But again, this works out correctly; the "then" and "else" blocks are compiled to instructions that load that particular literal into a  node and leave it there. That's fine, if your language allows such statements.

The point I'm trying to make is, that all PAST nodes are equal. You don't need to think about the node types if you set a node as a child of some other parent node. Each PAST node is compiled into a number of PIR instructions.

Go with the control-flow
Now you know a bit more on PAST nodes, let's get our hands dirty and implement some more statement types. In the rest of this episode, we'll handle if-statements and throw-statements.

If-then-else
The first statement we're going to implement now is the if-statement. An if-statement has typically three parts (but this of course depends on the programming language): a conditional expression, a "then" part and an "else" part. Implementing this in Perl 6 rules and PAST is almost trivial:

Note that the optional  block is stored in the match object's " " field. If we hadn't written this  part, then   would have been an array, with   the " " part, and   the optional   part. Assigning the optional  block to a different field, makes the action method slightly easier to read.

Also note that the statement rule has been updated; a statement is now either an assignment or an if-statement. As a result, the action method statement now takes a key argument. The relevant action methods are shown below:

That's, easy, huh? First, we get the result objects for the conditional expression and the then part. Then, a new  node is created, and the   is set to 'if', meaning this node represents an if-statement. Then, if there is an "else" block, this block's result object is retrieved and added as the third child of the PAST node. Finally, the result object is set with the make function.

Result objects
At this point it's wise to spend a few words on the   function, the parse actions and how the whole PAST is created by the individual parse actions. Have another look at the action method if_statement. In the first two lines, we request the result objects for the conditional expression and the "then" block. When were these result objects created? How can we be sure they're there? The answer lies in the order in which the parse actions are executed. The special   symbol that triggers a parse action invocation, is usually placed at the end of the. For this input string: " " this implies the following order:

 * 1) parse TOP
 * 2) parse statement
 * 3) parse if_statement
 * 4) parse expression
 * 5) parse integer
 * 6) create
 * 7) parse block
 * 8) parse statement
 * 9) parse assignment
 * 10) parse identifier
 * 11) create
 * 12) parse integer
 * 13) create
 * 14) create
 * 15) create   (in action method block)
 * 16) create
 * 17) create   (in action method TOP)

As you can see, PAST nodes are created in the leafs of the parse tree first, so that later, action methods higher in the parse tree can retrieve them.

Throwing Exceptions
The grammar rule for the "throw" statement is really quite easy, but it's useful to discuss the parse action, as it shows the use of generating custom PIR instructions. First the grammar rule:

rule throw_statement { 'throw' {*}   }

I assume you know how to update the "statement" rule by now. The throw statement will compile down to Parrot's "throw" instruction, which takes one argument. In order to generate a custom Parrot instruction, the instruction can be specified in the :pirop attribute when creating a PAST::Op node. Any child nodes are passed as arguments to this instruction, so we need to pass the result object of the expression being thrown as a child of the PAST::Op node representing the "throw" instruction.

method throw_statement($/) { make PAST::Op.new( $( $ ),                          :pirop('throw'),                           :node($/) ); }

What's Next?
In this episode we implemented two more statement types of Squaak. You should get a general idea of how and when PAST nodes are created, and how they can be retrieved sub (parse) trees. In the next episode we'll take a closer look at variable scope and subroutines.

In the mean time, I can imagine some things are not too clear. In case you're lost, don't hesitate to leave comment, and I'll try to answer (as far as my knowledge goes).


text:
Parrot Virtual Machine/Squaak Tutorial/Variable Declaration and Scope

Episode 4 discussed the implementation of some statement types, such as the if-statement. In this episode we'll talk about variable declarations and scope handling. It's going to be a long story, so take your time to read this episode.

Globals, locals and default values
Squaak variables have one of two scopes: either they're global, or they're local. In order to create a global variable, you just assign some expression to an identifier (which hasn't been declared as a local). Local variables, on the other hand, must be declared using the   keyword. In other words, at any given point during the parsing phase, we have a list of variables that are known to be local variables. When an identifier is parsed, it is looked up and if found, its scope is set to local. If not, its scope is assumed to be global. When using an uninitialized variable, its value is set to an object called  . Some examples are shown below.

x = 42            # x was not declared, so it is global var k = 10        # k is local and initialized to 10 a + b             # neither a nor b was declared; # both default to the value "Undef"

Scoping and Symbol Tables
Earlier we mentioned the need to store declared local variables. In compiler jargon, such a data structure to store declarations is called a symbol table. For each individual scope, there's a separate symbol table.

Squaak has a so-called do-block statement, that is defined below.

rule do_block { 'do' 'end' {*}   }

Each do-block defines a new scope; local variables declared between the " " and " " keywords are local to that block. An example to clarify this is shown below:

do     var x = 1 print(x)     # prints 1 do       var x = 2 print(x)   # prints 2 end print(x)     # prints 1 end

So, each do/end pair defines a new scope, in which any declared variables hide variables with the same name in outer scopes. This behavior is common in many programming languages. The PCT has built-in support for symbol tables; a  object has a method   that can be used to enter new symbols and query the table for existing ones. In PCT, a  object represents a scope. There are two s:   and  . An  block can be used to represent the blocks of statements in an do-block statement, for instance:

do       block end

When executing this statement, block is executed immediately. A  block, on the other hand, represents a block of statements that can be invoked at a later point. Typically these are subroutines. So, in this example:

sub foo(x) print(x) end

a  object is created for the subroutine. The  is set to , as the subroutine is defined, not executed (immediately). For now you can forget about the, but now that I've told you, you'll recognize it when you see it. We'll come back to it in a later episode.

Implementing Scope
So, we know how to use global variables, declare local variables, and about  objects representing scopes. How do we make our compiler to generate the right PIR instructions? After all, when handling a global variable, Parrot must handle this differently from handling a local variable. When creating  nodes to represent the variables, we must know whether the variable is a local or a global variable. So, when handling variable declarations (of local variables; globals are not declared), we need to register the identifier as a local in the current block's symbol table. First, we'll take a look at the implementation of variable declarations.

Variable declaration
The following is the grammar rule for variable declarations. This is a type of statement, so I assume you know how to extend the statement rule to allow for variable declarations.

rule variable_declaration { 'var' ['=' ]? {*}   }

A local variable is declared using the   keyword, and has an optional initialization expression. If the latter is missing, the variable's value defaults to the undefined value called  . Let's see what the parse action looks like:

method variable_declaration($/) { # get the PAST for the identifier my $past := $( $ );

# this is a local (it's being defined) $past.scope('lexical');

# set a declaration flag $past.isdecl(1);

# check for the initialization expression if $ { # use the viviself clause to add a           # an initialization expression $past.viviself( $($ [0]) ); }       else { # no initialization, default to "Undef" $past.viviself('Undef'); }       make $past; }

Well, that wasn't too hard, was it? Let's analyze what we just did. First we retrieved the PAST node for the identifier, which we then decorated by setting its scope to  (a local variable is said to be lexically scoped, hence  ), and setting a flag indicating this node represents a declaration. So, besides representing variables in other statements (for instance, assignments), a   node is also used as a declaration statement.

Earlier in this episode we mentioned the need to register local variables in the current scope block when they are declared. So, when executing the parse action for variable-declaration, there should already be a   node around, that can be used to register the symbol being declared. As we learned in Episode 4, PAST nodes are created in a depth-first fashion; the leafs are created first, and then the nodes "higher" in the parse tree. This implies that a   node is created after the statement nodes (which   is) that will be the children of the block. In the next section we'll see how to solve this problem.

Implementing a scope stack
In order to make sure that a  node is created before any statements are parsed (and their parse actions are executed -- these might need to enter symbols in the block's symbol table), we add a few extra parse actions. Let's take a look at them.

rule TOP { {*}                             #= open *       [ $ || <.panic: syntax error> ] {*}                             #= close }

We now have two parse actions for, which are differentiated by an additional key parameter. The first parse action is executed before any input is parsed, which is particularly suitable for any initialization actions you might need. The second action (which was already there) is executed after the whole input string is parsed. Now we can create a  node before any statements are parsed, so that when we need the current block, it's there (somewhere, later we'll see where exactly). Let's take a look at the parse action for.

method TOP($/, $key) { our $?BLOCK; our @?BLOCK;

if $key eq 'open' { $?BLOCK := PAST::Block.new( :blocktype('declaration'),                                     :node($/) ); @?BLOCK.unshift($?BLOCK); }      else { # key is 'close' my $past := @?BLOCK.shift;

for $ { $past.push( $( $_ ) ); }         make $past; }   }

Let's see what's happening here. When the parse action is invoked for the first time (when  equals  ), a new   node is created and assigned to a strange-looking (if you don't know Perl, like me. Oh wait, this is Perl. Never mind..) variable called. This variable is declared as " ", which means that it is a package variable. This means that the variable is shared by all methods in the same package (or class), and, equally important, the variable is still around after the parse action is done. Please refer to the Perl 6 specification for more semantics on "our". The variable  holds the current block. After that, this block is unshifted onto another funny-looking variable, called. This variable has a "@" sigil, meaning this is an array. The  method puts its argument on the front of the list. In a sense, you could think of the front of this list as the top of a stack. Later we'll see why this stack is necessary.

This  variable is also declared with " ", meaning it's also package-scoped. However, as we call a method on this variable, it should have been already created; otherwise you'd invoke the method on an undefined ("Undef") variable. So, this variable should have been created before the parsing starts. We can do this in the compiler's main program,. Before doing so, let's take a quick look at the " " part of the parse action for, which is executed after the whole input string is parsed. The  node is retrieved from , which makes sense, as it was created in the first part of the method and unshifted on. Now this node can be used as the final result object of. So, now we've seen how to use the scope stack, let's have a look at its implementation.

A List Class
We'll implement the scope stack as a ResizablePMCArray object. This is a built-in PMC type. However, this built-in PMC does not have any methods; in PIR it can only be used as an operand of the built-in shift and unshift instructions. In order to allow us to write this as method calls, we create a new subclass of ResizablePMCArray. The code below creates the new class and defines the methods we need.

1 .namespace 2 .sub 'initlist' :anon :init :load 3  subclass $P0, 'ResizablePMCArray', 'List' 4  new $P1, 'List' 5  set_hll_global ['Squaak';'Grammar';'Actions'], '@?BLOCK', $P1 6 .end 7 .namespace ['List'] 8 .sub 'unshift' :method 9  .param pmc obj 10  unshift self, obj 11 .end 12 .sub 'shift' :method 13  shift $P0, self 14  .return ($P0) 15 .end

Well, here you have it: part of the small amount of PIR code you need to write for the Squaak compiler (there's some more for some built-in subroutines, more on that later). Let's discuss this code snippet in more detail (if you know PIR, you could skip this section). Line 1 resets the namespace to the root namespace in Parrot, so that the sub  is stored in that namespace. The sub  defined in lines 2-6 has some flags:   means that the sub is not stored by name in the namespace, implying it cannot be looked up by name. The  flag means that the sub is executed before the main program (the "main" sub) is executed. The  flag makes sure that the sub is executed if this file was compiled and loaded by another file through the   instruction. If you don't understand this, no worries. You can forget about it now. In any case, we know for sure there's a List class when we need it, because the class creation is done before running the actual compiler code.

Line 3 creates a new subclass of ResizablePMCArray, called "List". This results in a new class object, which is left in register, but it's not used after that. Line 4 creates a new List object, and stores it in register. Line 5, stores this List object by name of " " (that name should ring a bell now...) in the namespace of the Actions class. The semicolons in between the several key strings indicate nested namespaces. So, lines 4 and 5 are important, because the create the  variable and store it in a place that can be accessed from the action methods in the Actions class.

Lines 7-11 define the unshift method, which is a method in the "List" namespace. This means that it can be invoked as a method on a List object. As the sub is marked with the  flag, the sub has an implicit first parameter called "self", which refers to the invocant object. The unshift method invokes Parrot's unshift instruction on self, passing the obj argument as the second operand. So, obj is unshifted onto self, which is the List object itself.

Finally, lines 12-15 define the "shift" method, which does the opposite of "unshift", removing the first element and returning it to its caller.

Storing Symbols
Now, we set up the necessary infrastructure to store the current scope block, and we created a datastructure that acts as a scope stack, which we will need later. We'll now go back to the parse action for variable_declaration, because we didn't enter the declared variable into the current block's symbol table yet. We'll see how to do that now. First, we need to make the current block accessible from the method variable_declaration. We've already seen how to do that, using the "our" keyword. It doesn't really matter where in the action method we enter the symbol's name into the symbol table, but let's do it at the end, after the initialization stuff. Naturally, we're only going to enter the symbol if it's not there already; duplicate variable declarations (in the same scope) should result in an error message (using the panic method of the match object). The code to be added to the method variable_declaration looks then like this:

method variable_declaration($/) { our $?BLOCK;

# get the PAST node for identifier

# set the scope and declaration flag

# do the initialization stuff

# cache the name into a local variable my $name := $past.name;

if $?BLOCK.symbol( $name ) { # symbol is already present $/.panic("Error: symbol " ~ $name                  ~ " was already defined.\n"); }       else { $?BLOCK.symbol( $name, :scope('lexical') ); }

make $past; }

What's Next?
With this code in place, variable declarations are handled correctly. However, we didn't update the parse action for identifier, which creates the PAST::Var node and sets its scope; currently all identifiers' scope is set to 'package' (which means it's a global variable). As we already covered a lot of material in this episode, we'll leave this for the next episode. In the next episode, we'll also cover subroutines, which is another important aspect of any programming language. Hope to catch you later!


text:
Parrot Virtual Machine/Squaak Tutorial/Scope and Subroutines

In Episode 5, we looked at variable declarations and implementing scope. We covered a lot of information then, but did not tell the full story, in order to keep that post short. In this episode we'll address the missing parts, which will also result in implementing subroutines.

Variables
In the previous episode, we entered local variables into the current block's symbol table. As we've seen earlier, using the do-block statement, scopes may nest. Consider this example:

do      var x = 42 do         print(x) end end

In this example, the print statement should print 42, even though x was not declared in the scope where it is referenced. How does the compiler know it's still a local variable? That's simple: it should look in all scopes, starting at the innermost scope. Only when the variable is found in any scope, should its scope be set to "lexical", so that the right instructions are being generated.

The solution I came up with is shown below. Please note that I'm not 100% sure if this is the "best" solution, but my personal understanding of the PAST compiler is limited. So, while this solution works, I may teach you the wrong "habit". Please be aware of this.

method identifier($/) { our @?BLOCK;

my $name := ~$ ; my $scope := 'package'; # default value

# go through all scopes and check if the symbol # is registered as a local. If so, set scope to       # local. for @?BLOCK { if $_.symbol($name) { $scope := 'lexical'; }       }

make PAST::Var.new( :name($name),                           :scope($scope),                            :viviself('Undef'),                            :node($/) ); }

Viviself
You might have noticed the viviself attribute before. This attribute will result in extra instructions that will initialize the variable if it doesn't exist. As you know, global variables spring into life automatically when they're used. Earlier we mentioned that uninitialized variables have a default value of "Undef": the viviself attribute does this. For local variables, we use this mechanism to set the (optional) initialization value. When the identifier is a parameter, the parameter will be initialized automatically if it doesn't receive a value when the subroutine it belongs to is invoked. Effectively this means that all parameters in Squaak are optional!

Subroutines
We already mentioned subroutines before, and introduced the  node type. We also briefly mentioned the  attribute that can be set on a   node, which indicates whether the block is to be executed immediately (for instance, a do-block or if statement) or it represents a declaration (for instance, subroutines). Let us now look at the grammar rule for subroutine definitions:

rule sub_definition { 'sub' *       'end' {*}   }

rule parameters { '(' [ [',' ]* ]? ')'       {*}    }

This is rather straightforward, and the action methods for these rules are quite simple, as you will see. First, however, let's have a look at the rule for sub definitions. Why is the sub body defined as  and not as a  ? Surely, a subroutine defines a new scope, which was already covered by Well, you're right in that. However, as we will see, by the time that a new  node would be created, we are too late! The parameters would already have been parsed, and not entered into the block's symbol table. That's a problem, because parameters are most likely to be used in the subroutine's body, and as they are not registered as local variables (which they are), any usage of parameters would not be compiled down to the right instructions to fetch any parameters.

So, how do we solve this in an efficient way?

The solution is simple. The only place where parameters live, is in the subroutine's body, represented by a  node. Why don't we create the  node in the action method for the   rule. By doing so, the block is already in place and the parameters are registered as local symbols right in time. Let's look at the action methods.

method parameters($/) { our $?BLOCK; our @?BLOCK;

my $past := PAST::Block.new( :blocktype('declaration'),                                    :node($/) );

# now add all parameters to this block for $ { my $param := $( $_ ); $param.scope('parameter'); $past.push($param);

# register the parameter as a local symbol $past.symbol($param.name, :scope('lexical')); }

# now put the block into place on the scope stack $?BLOCK := $past; @?BLOCK.unshift($past);

make $past; }

method sub_definition($/) { our $?BLOCK; our @?BLOCK;

my $past := $( $ ); my $name := $( $ );

# set the sub's name $past.name( $name.name );

# add all statements to the sub's body for $ { $past.push( $( $_ ) ); }

# and remove the block from the scope # stack and restore the current block @?BLOCK.shift; $?BLOCK := @?BLOCK[0];

make $past; }

First, let's check out the parse action for parameters. First, a new  node is created. Then, we iterate over the list of identifiers (which may be empty), each representing a parameter. After retrieving the result object for a parameter (which is just an identifier), we set its scope to "parameter", and we add it to the block object. After that, we register the parameter as a symbol in the block object, specifying the scope as "lexical". Parameters are just a special kind of local variables, and there's no difference in a parameter and a declared local variable in a subroutine, except that a parameter will usually be initialized with a value that is passed when the subroutine is invoked.

After handling the parameters, we set the current block (referred to by our package variable ) to the   node we just created, and push it on the scope stack (referred to by our package variable  ).

After the whole subroutine definition is parsed, the action method  is invoked. This will retrieve the result object for parameters, which is the  node that will represent the sub. After retrieving the result object for the sub's name, we set the name on the block node, and add all statements to the block. After this, we pop off this block node of the scope stack, and restore the current block.

Pretty easy, huh?

Subroutine invocation
Once you defined a subroutine, you'll want to invoke it. In the exercises of Episode 5, we already gave some tips on how to create the PAST nodes for a subroutine invocation. In this section, we'll give a complete description. First we'll introduce the grammar rules.

rule sub_call { {*}   }

Not only allows this to invoke subroutines by their name, you can also store the subroutines in an array or hash field, and invoke them from there. Let's take a look at the action method, which is really quite straightforward.

method sub_call($/) { my $invocant := $( $ ); my $past    := $( $ ); $past.unshift($invocant); make $past; }

method arguments($/) { my $past := PAST::Op.new( :pasttype('call'), :node($/) ); for $ { $past.push( $( $_ ) ); }       make $past; }

The result object of the sub_call method should be a PAST::Op node (of type 'call'), which contains a number of child nodes: the first one is the invocant object, and all remaining children are the arguments to that sub call.

In order to "move" the result objects of the arguments to the  method, we create the PAST::Op node in the method arguments, which is then retrieved by. In, the invocant object is set as the first child (using unshift). This is all too easy, isn't it? :-)

What's Next?
In this episode we finished the implementation of scope in Squaak, and implemented subroutines. Our language is coming along nicely! In the next episode, we'll explore how to implement operators and an operator precedence table for efficient expression parsing.

In the mean time, should you have any problems or questions, don't hesitate to leave a comment!


text:
Parrot Virtual Machine/Squaak Tutorial/Operators and Precedence

Up till now, we've implemented a great deal of the Squaak language. We've seen assignments, control-flow statements, variable declarations and scope, subroutines and invocation. Our expressions have been limited so far to singular values, such as string literals and integer constants. In this episode, we'll enhance Squaak so it can handle operators, so you can construct more complex expressions.

Operators, precedence and parse trees
We will first briefly introduce the problem with recursive-descent parsers (which parsers generated with the PCT are) when parsing expressions. Consider the following mini-grammar, which is a very basic calculator.

rule TOP { *   }

rule expression { }

rule term { [ ]*    }

token addop { '+' | '-' }

rule factor { [ ]*    }

token mulop { '*' | '/' | '%' }

rule value{ |       | '(' ')'    }

This basic expression grammar implements operator precedence by taking advantage of the nature of a recursive-descent parser (if you haven't seen the word, google it). However, the big disadvantage of parsing expressions this way, is that the parse trees can become quite large. Perhaps more importantly, the parsing process is not very efficient. Let's take a look at some sample input. We won't show the parse trees as shown in Episode 2, but we'll just show an outline.

input: 42 results in this parse tree:

TOP expression term factor value number 42

As you can see, the input of this single number will invoke 6 grammar rules before parsing the actual digits. Not that bad, you might think.

input: "1 + 2" results in this parse tree (we ignore the operator for now):

TOP expression term factor | value |  number |    1          factor value number 2

Only a few more grammar rules are invoked, not really a problem either.

input: "(1 + 2) * 3" results in this parse tree:

TOP expression term factor value | expression |  term |  | factor |  |   value |  |     number |  |       1            |   term |    factor |      value |        number |          2            value number 3

Right; 16 grammar rules just to parse this simple input. I'd call this slightly inefficient. The point is, implementing operator precedence using a recursive-descent parser is somewhat problematic, and given the fact there are better methods to parse expressions like these, not the way to go. Check out this nice explanation or google it.

Bottom-up parsing and stacks: operator tables
I would like to explain to you how bottom-up parsing works for expressions (or bottom-up parsers in general; Yacc/Bison are parser generators that generate bottom-up parsers for your grammar specification), taking operator precedence into account. However, it's been about 6 years that I did this in a CS class, and I don't remember the particular details. If you really want to know, check out the links at the end of the previous section. It's actually worth checking out. For now, I'll just assume you know what the problem is, so that I'll introduce the solution for PCT-based compilers immediately. At some point when parsing your input, you might encounter an expression. At this point, we'd like the parser to switch from top-down to bottom-up parsing. The Parrot Grammar Engine supports this, and is used as follows:

rule expression is optable { ... }

Note that we used the word "expression" here, but you can name it anything. This declares that, whenever you need an expression, the bottom-up parser is activated. Of course, this "optable" must be populated with some operators that we need to be able to parse. This can be done by declaring operators as follows:

proto 'infix:*' is tighter('infix:+') { ... }

This defines the operator "*" (the "infix:" is a prefix that tells the operator parser that this operator is an infix operator; there are other types, such as prefix, postfix and others). The "is tighter" clause tells that the "*" operator has a higher precedence than the "+" operator. As you could have guessed, there are other clauses to declare equivalent precedence ("is equiv") and lower precedence ("is looser").

It is very important to spell all clauses, such as "is equiv" correctly (for instance, not "is equil"), otherwise you might get some cryptic error message when trying to run your compiler. See the references section for the optable guide, that has more details on this.

Of course, the expression parser does not just parse operators, it must also parse the operands. So, how do we declare the most basic entity that represents an operand? It can be anything, from a basic integer-constant, a function call, or even a function definition (but adding two function definition doesn't really make sense, does it?). The operands are parsed in a recursive-descent fashion, so somewhere the parser must switch back from bottom-up (expression parsing) to top-down. To declare this "switch-back" point, write:

proto 'term:' is tighter('prefix:-') is parsed(&term)      { ... }

The name "term:" is a built-in name of the operator bottom-up parser; it is invoked every time a new operand is needed. The "is parsed" clause tells the parser that "term" (which accidentally looks like "term:", but you could also have named it anything else) parses the operands.

Note: it is very important to add a "is tighter" clause to the declaration of the "term:" rule. Otherwise your expression parser will not work! My knowledge here is a bit limited, but I usually define it as "is tighter" relative to the tightest operator defined.

Squaak Operators
We have defined the entry and exit point of the expression (bottom-up) parser, now it's time to add the operators. Let's have a look at Squaak's operators and their precedence. The operators are listed with decreasing precedence (so that high-precedence operators are listed at the top). (I'm not sure if this precedence table is common compared to other languages; some operators may have a different precedence w.r.t. other operators than you're used to. At least the mathematical operators are organized according to standard math rules).

unary "-" unary "not" * / %   + - ..    < <= >= > != ==    and or

(".." is the string concatenation operator). Besides defining an entry and exit point for the expression parser, you need to define some operator as a reference point, so that other operators' precedence can be defined relative to that reference point. My personal preference is to declare the operator with the lowest precedence as the reference point. This can be done like this:

proto 'infix:or' is precedence('1') { ... }

Now, other operators can be defined:

proto 'infix:and' is tighter('infix:or') { ... }   proto 'infix:<' is tighter('infix:and') { ... }   proto 'infix:+' is tighter('infix:<') { ... }   proto 'infix:*' is tighter('infix:+') { ... }   proto 'prefix:not' is tighter('infix:*') { ... }   proto 'prefix:-' is tighter('prefix:not') { ... }

Note that some operators are missing. See the exercises section for this. For more details on the use of the optable, check out  in the Parrot repository.

Short-circuiting logical operators
Squaak has two logical operators: and and or; and results true if and only if both operands evaluate to true, while or results true if at least one of its operands evaluates to true. Both operands are short-circuited, which means that they don't evaluate both operands if that's unnecessary. For instance, if the first operand of the and operator evaluates to false, then there's no need to evaluate the second operand, as the final result of the and-expression cannot become true anymore (remember: both operands must evaluate to true).

Let's think about how to implement this. When evaluating an and-expression, we first evaluate the first operand, and if it's true, only then does it make sense to evaluate the second operand. This behavior looks very much the same as an if-statement, doesn't it? In an if-statement, the first child is always evaluated, and if true, the second child (the "then" block) is evaluated (remember, the third child -- the "else" clause -- is optional). It would be great to be able to implement the and operator using a  node. Well, you can, using the " " clause! Here's how:

proto 'infix:and' is tighter('infix:or') is pasttype('if') { ... }

So what about the or operator? When evaluating an or-expression, the first operand is evaluated. If it evaluates to true, then there's no need to evaluate the second operand, as the result of the or-expression is already true! Only if the first operand evaluates to false, is it necessary to evaluate the second child. Mmmmm.... what we're saying here is, unless the first operand evaluates to true, evaluate the second child. Guess what pasttype you'd need for that!

Operators PAST types and PIR instructions
In the previous section, we introduced the "pasttype" clause that you can specify. This means that for that operator (for instance, the "and" operator we discussed), a  node is created. What happens if you don't specify a pasttype?

In that case a default PAST::Op node is created, and the default pasttype is 'call'. In other words, a PAST::Op node is created that calls the declared operator. For instance, the "infix:+" operator results in a call to the subroutine "infix:+". This means you'll need to implement subroutines for each operator. Now, that's a bit of a shame. Obviously, some languages have very exotic semantics for the "+" operator, but many languages just want to use Parrot's built-in add instruction. How do we achieve that? Instead of adding a "pasttype" clause, specify a "pirop" clause. The "pirop", or "PIR operator", clause tells the code generator what operator should be generated. Instead of generating a subroutine invocation with the operands as arguments, it will generate the specified instruction with the operator's operands as arguments. Neat huh? Let's look at an example:

proto 'infix:+' is tighter('infix:<') is pirop('n_add') { ... }

This specifies to use the " " instruction, which tells Parrot to create a new result object instead of changing one of the operands. Why not just the "add" instruction (which takes two operands, updating the first), you might think. Well, if you leave out this "is pirop" stuff, this will be generated:

$P12 = "infix:+"($P10, $P11)

You see, three registers are involved. As we mentioned before, PCT does not do any optimizations. Therefore, instead of the generated instruction above, it just emit the following:

n_add $P12, $P10, $P11

which means that the PMCs in registers  and   are added, and assigned to a newly created PMC which is stored in register.

To circumfix or not to circumfix
Squaak supports parenthesized expressions. Parentheses can be used to change the order of evaluation in an expression, just as you're probably have seen this in other languages. Besides infix, prefix and postfix operators, you can define circumfix operators, which is specified with the left and right delimiter. This is an ideal way to implement parenthesized expressions:

proto 'circumfix:' is looser('infix:+') is pirop('set') { ... }

By default, a subroutine invocation will be generated for each operator, in this case a call to " ". However, we are merely interested in the expression that has been parenthesized. The subroutine would merely return the expression. Instead, we can use the pirop attribute to specify what PIR operation should be generated; in this case that is the "set" operation, which sets one register to the contents of another.

This solution works fine, except that "set" instructions are a bit of a waste. What happens is, the contents of some register is just copied to another register, which is then used in further code generation. This "set" instruction might as well be optimized away. Currently, there are no optimizations implemented in the PCT.

There is an alternative solution for adding grammar rules for the parenthesized expressions, by adding it as an alternative of term. The grammar rule term then ends up as:

rule term { |  {*}    #= float_constant |  {*}  #= integer_constant |  {*} #= string_constant | {*}           #= primary | '(' ')' {*} #= expression }

Of course, although we save one generated instruction, the parser will be slightly more inefficient, for reasons that we discussed at the beginning of this episode. Of course, you are free to decide for yourself how to implement this; this section just explains both methods. At some point, optimizations will be implemented in the PCT. I suspect "useless" instructions (such as the "set" instruction we just saw) will then be removed.

Expression parser's action method
For all grammar rules we introduced, we also introduced an action method that is invoked after the grammar rule was done matching. What about the action method for the optable? Naturally, there must be some actions to be executed.

Well, there is, but to be frank, I cannot explain it to you. Every time I needed the action method for an optable, I just copied it from an existing actions file. Of course, the action method's name should match the name of the optable (the rule that has the "is optable" clause). So, here goes:

method expression($/, $key) { if ($key eq 'end') { make $($ ); }       else { my $past := PAST::Op.new(                         :name($ ),                          :pasttype($  ),                          :pirop($  ),                          :lvalue($  ),                          :node($/) ); for @($/) { $past.push( $($_) ); }           make $past; }   }

What's Next?
This episode covered the implementation of operators, which allows us to write complex expressions. By now, most of our language is implemented, except for one thing: aggregate data structures. This will be the topic of Episode 8. We will introduce the two aggregate data types: array and hashtables, and see how we can implement these. We'll also discuss what happens when we pass such aggregates as subroutine arguments, and the difference with the basic data types.