Re: Need advices for creating a proprietary language

Ondrej Tucny <>
12 Mar 1998 23:20:16 -0500

          From comp.compilers

Related articles
Need advices for creating a proprietary language (Mike) (1998-03-03)
Re: Need advices for creating a proprietary language (Lyn A Headley) (1998-03-06)
Re: Need advices for creating a proprietary language (1998-03-06)
Re: Need advices for creating a proprietary language (Joachim Durchholz) (1998-03-07)
Re: Need advices for creating a proprietary language (MC) (1998-03-07)
Re: Need advices for creating a proprietary language (Mark Harrison) (1998-03-07)
Re: Need advices for creating a proprietary language (Leif Nixon) (1998-03-12)
Re: Need advices for creating a proprietary language (Ondrej Tucny) (1998-03-12)
Re: Need advices for creating a proprietary language (Dupont de Dinechin Christophe) (1998-03-15)
Re: Need advices for creating a proprietary language (Laurentiu Badea) (1998-03-18)
Re: Need advices for creating a proprietary language (Andreas Kochenburger) (1998-03-30)
| List of all articles for this month |

From: Ondrej Tucny <>
Newsgroups: comp.compilers
Date: 12 Mar 1998 23:20:16 -0500
Organization: Compilers Central
References: 98-03-039
Keywords: design, practice

Lyn A Headley wrote
>Writing a compiler is very hard. If you have never studied the
> ....

Are you sure? I think writing a compiler is one of the easiest things,
I've ever done. I think you need about one week to practise the basic
algorithms and then you should be able to write a simple compiler. But
yes, you're true if you're writing something like Ada. I wrote a
compiler of a language may be nearsy as complex as Ada and it took me
two years.

Here's my original reply to this message. Originaly I've sent it
directly to the author, because it's pretty large.

> I'm looking on the net since 3 days, and now I know what means the words:
> parser, token recognition,error recovery, semantic analysis, formal
> concepts, regular expressions, context-free grammars, top_down/bottom-up
> parsing, etc...
> But I'm submerged with url from american universities ( that
> present the content of the compiler courses !!!
> I'm beeing driving crazy.
> And all the rest is about how to use BISON,LEX,YACC, and stuff like that.
> I don't think I must have to dive in such programs for creating my
> compilator ??

I think you're the first man I've ever met on the comp.compilers
newsgroup, who's not afraid to write a compiler. I mean real
programmers don't use yacc/lex/... and do all the work from scratch. I
think tools like yacc want solve all the problems and so become
totally unusable, but stop talking about stupid tools a let's write a

STEP 1: defining the grammar of the language - the syntax rules

Basically, you write down what each part of a source code means, like

                  Procedure ::= "procedure" Identifier [ Formal parameters ]
                                                      = { Declaration } "begin" { Statement } "end"

So what means what:
        Procedure, Identifier, Formal parameters - syntactic categories
        ::= - just a symbol, kind of "assignment" (syntactic category
                is ...)
        [ ] - means optional part (procedure
        { } - means repetition 0 to (nearly) infinity times
        "procedure", "begin", ... - keywords
        | - means or: a | b - there will be either a or b (not used here)

symbols are:
        1) terminal - like keyword, Identifier, number - don't have
special internal structure and are recognized by the
lexical analyzer
        2) non-terminal - like Procedure, Formal parameters, Statement - are
              represented by a sequence of another non-terminals and terminals,
              these are recognized by the syntactic analyzer

I'll define a simple expression and an assignment statement:

Expression ::= Simple expression [ Relational operator Simple expression
Relation operator ::= < | > | = | <> | <= | >=
Simple expression ::= Factor { Addition operator Factor }
Addition operator ::= + | -
Factor ::= Term { Multiplication operator Term }
Multiplication operator ::= * | div | mod
Term ::= Identifier | number | ( Expression )

Assignment statement ::= Identifier := Expression

Now you're ready to start coding;

STEP 2: writing procedures for lexical analysis

You'll new two procedures for working with the source code: getlex and
ungetlex. The first one retrieves a lexical element from the source
code, the second one will return it back "in the source". The code will
be like as follows:

    -- representation of lexical elements
    lexelem = enum
        lex_eof, -- end of file
        lex_id, -- identifier
        lex_num, -- integer number
        -- keywords
        lex_begin, -- keyword "begin"
        lex_end, -- keyword "end"
        -- special symbols
        lex_plul, -- "+"
        lex_minus, -- "-"
        lex_assign, -- ":="
        end enum;

    -- unget buffer
    lastvalid : boolean := false;
    last : lexelem;

procedure getlex return lexelem =
    if lastvalid
        -- next lexical element was already read and is stored in the unget

        -- get next lexical element from the source code
            -- easy to implement, identifier starts with a letter, number with
a -- digit, spaces are ignored etc.
            -- you might find useful writing procedures getchar and ungetchar
            -- the same manner as (un)getlex is writen for reading the source
        end if;

    -- prepare for ungetlex
    end getlex;

procedure ungetlex =
    end ungetlex;

Note: as you can see I've defined a lex_eof symbol representing the end
of file, this is quite useful, because you don't have to check for such
stupid errors.

This is all you need for comfortable work with the source code.

STEP 3: writing the compiler

You just turn all the syntactic rules into procedures and add semantic
rules and code generation.

First try writing a simple expression parser. All the other work is very
similar. Define a tree structure, that will represent the expression:

    -- "operator"
    expoper = enum
          exp_id, -- identifier (=variable)
          exp_num, -- number
          exp_plus, -- addition
          exp_minus, -- subtraction
          end enum;

    pnode = ^node;
    node = record
          exp : expoper; -- "operator" this node represents
          left : pnode; -- left subtree
          right : pnode; -- right subtree
          end node;

you'll need a
        procedure make_tree_a_left_subtree(t : ref pnode)
that will create a new node, assign t as its left subtree and return the
new node.

Finally write the code:

procedure Expression return pnode =

    lex : lexelem;

    -- parse the first Simple expression

    -- is there a relational operator ?
    if lex in [lex_eq,lex_not_eq, ... ]
        -- yes
            -- prepare the tree
            result^.oper:="exp_eq, exp_not_eq, ... regarding to lex";

            -- parse the next Simple expression

        -- no
            -- return the lexical element back
        end if;
    end Expression;

procedure Simple_expression return pnode =

    lex : lexelem;

    -- parse the first Factor

    -- try reading an additional operator

    while lex in [lex_plus,lex_minus] loop
        -- prepare the tree
        result^.oper:="exp_plus, exp_minus regarding to lex";

        -- parse the next Factor

        -- try next operator
        end loop;

    -- last element wasn't used, return back
    end Simple_expression;


procedure Term return pnode =

    lex : lexelem;

    -- get next lexical element

    case lex of
        -- identifier
        when lex_id do result:="create a node exp_id";

        -- number
        when lex_num do result:="create a node exp_num";

        -- expression in parenthesis
        when lex_left_par do
                -- parse expression
                -- must be followed by the right parenthesis
                if lex<>lex_right_par then "error: e.g. raise an exception"; end

        -- no other elements are allowed here
        when others do "error: e.g.. raise an exception";
        end case;
    end Term;

The code above transforms expression a<b*(c+d+1) into a tree:

              a *
                              b +
                                              + 1
                              c d

Once you have this representation of an expression it's very easy to do
things like type compatibility checking, optimization (0*x --> 0) and
also code generation. You just evaluate the left subexpression than the
right subexpression and do the operation specified by the current node

        imm <address of a>
        imm <address of b>
        imm <address of c>
        imm <address of d>
        imm 1

I think this kind of evaluation is sometimes called "polish notation".
The instructions do the following:

        imm - stores immediate value on the stack (e.g.. a number or
        load - loads variable on the stack (gets address from stack)
        add - adds two numbers stored on the stack and pushes the result
on the stack
        mul - like add, but performs multiplication
        less - compares two numbers from stack a pushes boolean result

STEP 4: writing the interpreter

you just get the instructions and perform the actions like:

        case instr
            when imm do push("parameter of the instruction")
            when add do
            end case;

Note: implementing advanced features like SetAnimation: I don't
recommend you creating special purpose instructions, in future versions
it'll be hard to maintain. Better try using a construction like this:

          procedure SetAnimation (name : string) internal 1024;

and create a special internal procedure calling instruction that gets
two parameters: an index of the internal procedure and length of
so the operation will be as follows:

          when internal do
                  internal_proc_handler("index of internal procedure",
                          "address of parameter block");
                  pop_bytes_from_stack("length of parameters");

Doing it this way you get a language/interpreter usable for all you
other products.

That's all the knowledge you need for writing a simple compiler.

> Any help would be welcome.
> Thanks a lot,
> Mike.
> Programmer,
> Heliovisions Productions,
> Lyon/France

A&&L soft,
Prague/Czech Republic

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.