<commit_before>=pod

=head0 PCT: Parrot Compiler Tools

Z<CHP-8>

So far we've talked a lot about low-level Parrot programming with
PIR and PASM. However, the true power of Parrot is it's ability to
host programs written in high level languages such as Perl 6,
Python, Ruby, Tcl, and PHP. In order to write code in these languages
developers need there to be compilers that convert from the language
into PIR or PASM (or even directly convert to Parrot Bytecode).
People who have worked on compilers before may be anticipating us
to use terms like "Lex and Yacc" here, but we promise that we wont.

Instead of traditional lexical analyzers and parser-generators that
have been the mainstay of compiler designers for decades, Parrot
uses an advanced set of parsing tools called the Parrot Compiler
Tools (PCT)X<Parrot Compiler Tools>. PCT uses a subset of the Perl 6
programming language called I<Not Quite Perl>X<Not Quite Perl> (NQP)
and an implementation of the Perl 6 Grammar Engine X<Perl 6 Grammar
Engine> (PGE) to build compilers for Parrot. Instead of using
traditional low-level languages to write compilers, we can use a
modern dynamic language like Perl 6 to write it instead. On a more
interesting note, this means that the Perl 6 compiler is itself
being written in Perl 6, a mind-boggling process known as
C<bootstrapping>.

=head1 PCT Overview

PCT is a collection of classes which handle the creation of a
compiler and driver program for a high-level language. The
C<PCT::HLLCompiler> class handles building the compiler front end
while the C<PCT::Grammar>  and C<PCT::Grammar::Actions> classes handle
building the parser and lexical analyzer. Creating a new HLL compiler
is as easy as subclassing these three entities with methods specific
to that high-level language.

=head2 Grammars and Action Files

Creating a compiler using PCT requires three basic files, plus any
additional files needed to implement the languages logic and library:

=over 4

=item* A main file

The main file should contain the C<:main> function that is the driver
program for the compiler. Here, a new C<PCT::HLLCompiler> object is
instantiated, libraries are loaded, and necessary special global
variables are created. The driver program is typically written in PIR,
although thankfully they tend to be very short. Most of the action
happens elsewhere.

=item* A parser file

The grammar for the high level language is specified using the Perl 6
grammar engine (PGE) and is stored in a C<.pg> file. This file should
subclass the C<PCT::Grammar> class and implement all the necessary
rules to successfully parse the language.

=item* An actions file

Actions files are written in NQP. They take match objects generated by
the grammar file and convert them into an Abstract Syntax Tree (AST)
X<Abstract Syntax Tree;Parrot Abstract Syntax Tree;AST;PAST>
which is converted by PCT into PIR for compiling and execution.
The PIR implementation of these AST trees and nodes is called the
Parrot Abstract Syntax Tree (PAST).

=back

=head2 C<make_language_shell.pl>

=head2 Parsing Fundamentals

Compilers typically consist of three components: The lexical analyzer,
the parser, and the code generator. The lexical analyzer converts the
HLL input file into individual tokens. A token may consist of an
individual punctuation mark("+"), an indentifier ("myVar"), or a keyword
("while"), or any other artifact that cannot be sensibly broken down.
The parser takes a stream of these input tokens, and attempts to match
them against a given pattern, or grammar. The matching process orders
the input tokens into an abstract syntax tree (AST), which is a form that
the computer can easily work with. This AST is passed to the code
generator which converts it into code of the target language. For
something like the GCC C compiler, the target language is machine code.
For PCT and Parrot, the target language is PIR and PBC.

Parsers come in two general varieties: Top-down and bottom-up. Top-down
parsers start with a top-level rule, a rule which is supposed to
represent the entire input. It attempts to match various combination of
subrules until the entire input is matched. Bottom-down parsers, on the
other hand, start with individual tokens from the lexical analyzer and
attempt to combine them together into larger and larger patterns until
they produce a top-level token.

PGE itself is a top-down parser, although it also contains a bottom-up
I<operator precidence> parser, for things like mathematical expressions
where bottom-up methods are more efficient. We'll discuss both, and the
methods for switching between the two, throughout this chapter.

=head1 Driver Programs

=head2 C<HLLCompiler> class


=head1 Parrot Grammar Engine

The Parrot Grammar Engine X<Parrot Grammar Engine;PGE> is an
implementation of the Perl 6 grammar syntax in Parrot. The grammar
engine in Perl 6 is much more advanced and flexible then the regular
expression syntax of Perl 5. Since most other languages who implement
regular expressions use a copy (or a subset) of Perl 5's regular
expressions, PGE is much more powerful then those too.

PGE uses a recursive descent algorithm N<it also uses an operator
precedence parser, when you ask it nicely>which should be very familar
to users of the Perl 5 module C<Parse::RecDescent>. In fact, both were
originally designed by the same developer, <NAME>. Recursive<commit_msg>[Book] Added short sections about make_language_shell.pl and driver programs for new compilers<commit_after>=pod

=head0 PCT: Parrot Compiler Tools

Z<CHP-8>

So far we've talked a lot about low-level Parrot programming with
PIR and PASM. However, the true power of Parrot is it's ability to
host programs written in high level languages such as Perl 6,
Python, Ruby, Tcl, and PHP. In order to write code in these languages
developers need there to be compilers that convert from the language
into PIR or PASM (or even directly convert to Parrot Bytecode).
People who have worked on compilers before may be anticipating us
to use terms like "Lex and Yacc" here, but we promise that we wont.

Instead of traditional lexical analyzers and parser-generators that
have been the mainstay of compiler designers for decades, Parrot
uses an advanced set of parsing tools called the Parrot Compiler
Tools (PCT)X<Parrot Compiler Tools>. PCT uses a subset of the Perl 6
programming language called I<Not Quite Perl>X<Not Quite Perl> (NQP)
and an implementation of the Perl 6 Grammar Engine X<Perl 6 Grammar
Engine> (PGE) to build compilers for Parrot. Instead of using
traditional low-level languages to write compilers, we can use a
modern dynamic language like Perl 6 to write it instead. On a more
interesting note, this means that the Perl 6 compiler is itself
being written in Perl 6, a mind-boggling process known as
C<bootstrapping>.

=head1 PCT Overview

PCT is a collection of classes which handle the creation of a
compiler and driver program for a high-level language. The
C<PCT::HLLCompiler> class handles building the compiler front end
while the C<PCT::Grammar>  and C<PCT::Grammar::Actions> classes handle
building the parser and lexical analyzer. Creating a new HLL compiler
is as easy as subclassing these three entities with methods specific
to that high-level language.

=head2 Grammars and Action Files

Creating a compiler using PCT requires three basic files, plus any
additional files needed to implement the languages logic and library:

=over 4

=item* A main file

The main file should contain the C<:main> function that is the driver
program for the compiler. Here, a new C<PCT::HLLCompiler> object is
instantiated, libraries are loaded, and necessary special global
variables are created. The driver program is typically written in PIR,
although thankfully they tend to be very short. Most of the action
happens elsewhere.

=item* A parser file

The grammar for the high level language is specified using the Perl 6
grammar engine (PGE) and is stored in a C<.pg> file. This file should
subclass the C<PCT::Grammar> class and implement all the necessary
rules to successfully parse the language.

=item* An actions file

Actions files are written in NQP. They take match objects generated by
the grammar file and convert them into an Abstract Syntax Tree (AST)
X<Abstract Syntax Tree;Parrot Abstract Syntax Tree;AST;PAST>
which is converted by PCT into PIR for compiling and execution.
The PIR implementation of these AST trees and nodes is called the
Parrot Abstract Syntax Tree (PAST).

=back

=head2 C<make_language_shell.pl>

The Parrot repository contains a number of helpful utilities for doing
some common development and building tasks with Parrot. These utlities
are all currently written in Perl 5, although in future releases the
majority will likely be built in Perl 6 and run on Parrot directly. This
is a bootstrapping problem that the developers have not tackled yet.

One of the tools of use to new compiler designers and language implementers
is C<make_language_shell.pl>. C<make_language_shell.pl> is a tool for
automatically creating all the necessary stub files for creating a new
compiler for Parrot. It generates the driver file, parser grammar and
actions files, builtin functions stub file, makefile, and test harness.
All of these are demonstrative stubs and wil obviously need to be
edited furiously or even completely overwritten, but they give a good idea
of what is needed to start on development of the compiler.

C<make_language_shell.pl> is designed to be run from within the Parrot
repository file structure. It creates a subfolder in C</languages/>
with the name of your new language implementation. Typically a new
implementation of an existing language is not simply named after the
language, but is given some other descriptive name to let users know it
is only one implementation available. Consider the way Perl 5 distributions
are named things like "Active Perl" or "Strawberry Perl", or how Python
distributions might be "IronPython" or "VPython". If, on the other hand,
you are implementing an entirely new language, you don't need to give it
a fancy distribution name.

=head2 Parsing Fundamentals

Compilers typically consist of three components: The lexical analyzer,
the parser, and the code generator. The lexical analyzer converts the
HLL input file into individual tokens. A token may consist of an
individual punctuation mark("+"), an indentifier ("myVar"), or a keyword
("while"), or any other artifact that cannot be sensibly broken down.
The parser takes a stream of these input tokens, and attempts to match
them against a given pattern, or grammar. The matching process orders
the input tokens into an abstract syntax tree (AST), which is a form that
the computer can easily work with. This AST is passed to the code
generator which converts it into code of the target language. For
something like the GCC C compiler, the target language is machine code.
For PCT and Parrot, the target language is PIR and PBC.

Parsers come in two general varieties: Top-down and bottom-up. Top-down
parsers start with a top-level rule, a rule which is supposed to
represent the entire input. It attempts to match various combination of
subrules until the entire input is matched. Bottom-down parsers, on the
other hand, start with individual tokens from the lexical analyzer and
attempt to combine them together into larger and larger patterns until
they produce a top-level token.

PGE itself is a top-down parser, although it also contains a bottom-up
I<operator precidence> parser, for things like mathematical expressions
where bottom-up methods are more efficient. We'll discuss both, and the
methods for switching between the two, throughout this chapter.

=head1 Driver Programs

The driver program for the new compiler must create instances of the
various necessary classes that run the parser. It must also include
the standard function libraries, create global variables, and handle
commandline options. Most commandline options are handled by PCT, but
there are some behaviors that the driver program will want to
override.

PCT programs can, by default, be run in two ways: Interactive mode,
which is run one statement at a time in the console, and file mode which
loads and runs an entire file. For interactive mode, it is necessary
to specify information about the prompt that's used and the environment
that's expected. Help and error messages need to be written for the user
too. 

=head2 C<HLLCompiler> class


=head1 Parrot Grammar Engine

The Parrot Grammar Engine X<Parrot Grammar Engine;PGE> is an
implementation of the Perl 6 grammar syntax in Parrot. The grammar
engine in Perl 6 is much more advanced and flexible then the regular
expression syntax of Perl 5. Since most other languages who implement
regular expressions use a copy (or a subset) of Perl 5's regular
expressions, PGE is much more powerful then those too.

PGE uses a recursive descent algorithm N<it also uses an operator
precedence parser, when you ask it nicely>which should be very familar
to users of the Perl 5 module C<Parse::RecDescent>. In fact, both were
originally designed by the same developer, <NAME>. Recursive
{'fraction_non_alphanumeric': 0.037599696164071404, 'fraction_numerical': 0.0037219901253323206, 'mean_word_length': 4.784710017574692, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5358107', 'n_tokens_mistral': 3446, 'n_tokens_neox': 3226, 'n_words': 2078}