Archive

## Tag Cloud

3d account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio bash batch blog bookmarklet booting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compilers compiling compression css dailyprogrammer debugging demystification distributed computing documentation downtime electronics email embedded systems encryption es6 features event experiment external first impressions future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet io.js jabber javascript js bin labs learning library linux low level lua maintenance manjaro network networking node.js operating systems performance photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit reference release releases resource review rust secrets security series list server software sorting source code control statistics storage svg technical terminal textures three thing game three.js tool tutorial tutorials twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 xmpp xslt

## Routers: Essential, everywhere, and yet exasperatingly elusive

Now that I've finished my University work for the semester (though do have a few loose ends left to tie up), I've got some time on my hands to do a bunch of experimenting that I haven't had the time for earlier in the year.

In this case, it been tracking down an HTTP router that I used a few years ago. I've experimented with a few now (find-my-way, micro-http-router, and rill) - but all of them few something wrong with them, or feel too opinionated for my taste.

I'm getting slightly ahead of myself though. What's this router you speak of, and why is it so important? Well, it call comes down to application design. When using PHP, you can, to some extent, split your application up by having multiple files (though I would recommend filtering everything through a master index.php). In Node.JS, which I've been playing around with again recently, that's not really possible.

Unlike PHP, which gets requests handed to it from a web server like Nginx via CGI (Common Gateway Interface), Node.JS is the server. You can set up your very own HTTP server listening on port 9898 like this:

import http from 'http';
const http_server = http.createServer((request, response) => {
});
response.end("Hello, world!");
}).listen(9898, () => console.log("Listening on pot 9898"));

This poses a problem. How do we know what the client requested? Well, there's the request object for that - and I'm sure you can guess what the response object is for - but the other question that remains is how to we figure out which bit of code to call to send the client the correct response?

That's where a request router comes in handy. They come in all shapes and sizes - ranging from a bare-bones router to a full-scale framework - but their basic function is the same: to route a client's request to the right place. For example, a router might work a little bit like this:

import http from 'http';
import Router from 'my-awesome-router-library';

// ....

const router = new Router();

const http_server = http.createServer(router.handler()).listen(20202);

Pretty simple, right? This way, every route can lead to a different function, and each of those functions can be in a separate file! Very cool. It all makes for a nice and neat way to structure one's application, preventing any issues relating to any one file getting too big - whilst simultaneously keeping everything orderly and in its own place.

Except when you're picky like me and you can't find a router you like, of course. I've got some pretty specific requirements. For one, I want something flexible and unopinionated enough that I can do my own thing without it getting in the way. For another, I'd like first-class support for middleware.

What's middleware you ask? Well, I've only just discovered it recently, but I can already tell that's its a very powerful method of structuring more complex applications - and devastatingly dangerous if used incorrectly (the spaghetti is real).

Basically, the endpoint of a route might parse some data that a client has sent it, and maybe authenticate the request against a backend. Perhaps a specific environment needs to be set up in order for a request to be fulfilled.

While we could do these things in the end route, it would clutter up the code in the end route, and we'd likely have more boilerplate, parsing, and environment setup code than we have actual application logic! The solution here is middleware. Think of it as an onion, with the final route application logic in the middle, and the parsing, logging, and error handling code as the layers on the outside.

In order to reach the application logic at the centre, an incoming request must first make its way through all the layers of middleware that are in the way. Similarly, it must also churn through the layers of middleware in order to get out again. We could represent this in code like so:

// Middleware that runs for every request
router.use(middleware_error_handler);
router.use(middleware_request_logger);

// Decode all post data with middleware
// This won't run for GET / HEAD / PUT / etc. requests - only POST requests
router.post(middleware_decode_post_data);

// For GET requestsin under /inbox, run some middleware
router.get("/inbox", middleware_setup_user_area);

// Endpoint routes
// These function just like middleware too (i.e. we could
// pass the request through to another layer if we wanted
// to), but that don't lead anywhere else, so it's probably
// better if we keep them separate
router.any("/honeypot", route_spambot_trap);

router.post("/login", route_do_login);

Quite a neat way of looking at it, right? Lets take a look at some example middleware for our fictional router:

async function middleware_catch_errors(context, next) {
try {
await next();
} catch(error) {
console.error(error.stack);
"content-type": "text/plain"
});
// todo make this fancier
}
}

See that next() call there? That function call there causes the application to enter the next layer of middleware. We can have as many of these layers as we like - but don't go crazy! It'll cause you problems later whilst debugging.....

What I've shown here is actually very similar to the rill framework - it just has a bunch of extras tagged on that I don't like - along with some annoying limitations when it comes to defining routes.

To that end, I think I'll end up writing my own router, since none of the ones I've found will do the job just right. It kinda fits with the spirit of the project that this is for, too - teaching myself new things that I didn't know before.

If you're curious as to how a Node.JS application is going to fit in with a custom HTTP + WebSockets server written in C♯, then the answer is a user management panel. I'm not totally sure where this is going myself - I'll see where I end up! After all, with my track record, you're bound to find another post or three showing up on here again some time soon.

Until then, Goodnight!

Found this useful? Still got questions? Comment below!

## Shift-Reduce Parser Part 2: Building Furniture (1)

Hello and welcome! I got a bit distracted by other things as you can tell, but I'm back with part 2 of my series on building a shift-reduce parser. If you're not sure what I'm talking about, then I'd advise reading part 1 first and then coming back here. It might be a good idea to re-read it anyway, juts to refresh your memory :-)

Last time, we created some data classes to store the various rules and tokens that we'll be generating. Today, we're going to build on that and start turning a set of rules into a parse table. Let's introduce the rules we'll working with:

<start> ::= <expression>

<expression> ::= <expression> PLUS <value>
| <term>

<term> ::= <term> DIVIDE <value>
| <value>

<value> ::= <number>
| BRACKET_OPEN <expression> BRACKET_CLOSE

<number> ::= DIGIT
| <number> DIGIT

The above represents a very basic calculator-style syntax, which only supports adding and dividing. It's written in Backus-Naur Form, which is basically a standardised way of writing parsing rules.

To build a parse table, we first must understand what such a thing actually is. Let's take a look at an example:

state action goto
* + 0 1 $E B 0 s1 s2 3 4 1 r4 r4 r4 r4 r4 2 r5 r5 r5 r5 r5 3 s5 s6 goal 4 r3 r3 r3 r3 r3 5 s1 s2 7 6 s1 s2 8 7 r1 r1 r1 r1 r1 8 r2 r2 r2 r2 r2 _(Source: Adapted from the LR Parser on Wikipedia.)_ While it looks complex at first, let's break it down. There are 3 parts to this table: The state, the action, and the goto. The action and goto represent What should happen if a particular token is encountered. In this case, the input stream contains both terminal (i.e. DIGIT, DIVIDE, BRACKET_CLOSE, etc. in the case of our BNF above) and non-terminal (i.e. number, term, expression, etc. in the case of our BNF above) symbols - if understand it correctly, so there are actually 2 parts to the table here to make sure that both are handled correctly. We'll be connecting this to our lexer, which outputs only terminal symbols, so we should be ok I believe (if you know better, please post a comment below!). The state refers to the state in the table. As I've mentioned before, a given state may contain one or more configurations. It's these configurations that give rise to the actions in the table above, such as s2 (shift and then go to state 2) or r3 (reduce and jump to state 3). To use the table, the parser must know what state it's in, and then take a look across the top row for the next symbol it has in the token stream. Once found, it can follow it down to figure out what action it should take, as explained above. If there isn't an action in the box, then there must be an error in the input, as the table doesn't tell us what to do in this situation. To that end, we should try and generate a meaningful error message to help the user to find the mistake in the input (or the developer in the parser!). We're kind of getting ahead of ourselves here though. We need to build this table first, and to do that, we need to figure out which configurations go in which state. And, going down the rabbit hole, we need to know what a configuration is. Again, it's best if I demonstrate. Consider the following parsing rule from our example BNF at the beginning of this post: <value> ::= BRACKET_OPEN <expression> BRACKET_CLOSE A single configuration represent a possible state of the parser at a particular instant in time. I could split that above rule up like so: <value> ::= BRACKET_OPEN * <expression> BRACKET_CLOSE <value> ::= BRACKET_OPEN <expression> * BRACKET_CLOSE <value> ::= BRACKET_OPEN <expression> BRACKET_CLOSE * The asterisk represent where the parser might have gotten up to. Everything to the left is on the stack of the parser, and everything to the right hasn't happened yet. Since this isn't a top-level rule (in our example that honour goes to the rule for the start non-terminal), the parser will never be in a position where the first item there doesn't exist yet on the stack, so we can ignore the configuration in which the asterisk would be to the left of BRACKET_OPEN. Confused? Let me try and help here. Let's draw a diagram of how our parser is going to operate: _(Source: Made by me, but adapted from the LR Parser article on Wikipedia)_ Basically, the parser will be taking in the input token stream and either shift a new terminal token onto the stack, or reduce one or more existing tokens on the stack into a single non-terminal token, which replaces those existing tokens on the stack. The configurations above represent possible states of the stack (the bit to the left of the asterisk), and possible directions that the parser could take when parsing (the bit to th right of the asterisk). Finally, when the goal is reached, the output is returned to the caller (which, by the time we're done, should be a parse tree). Said tree can then be optimised and processed for whatever purpose we desire! With this knowledge, we can deduce that we can build the entire table by recursing over the tree of rules from the start state. That way, we'll visit every rule that we'll need to parse everything required to reach the goal state by recursing over all the rules for all the non-terminals referenced by all the rules we visit. We could even generate a warning if we detect that some rules don't connect to this 'tree'. Here's a tree of our example ruleset from the beginning of this post: It's a bit spaghetti-ish, but it should be legible enough :P This gives us an idea as to how we're going to tackle this. Taking into account the data classes we created in the last post, we need to make sure we keep the following in mind: 1. Since the main ShiftReduceParser class is going to hold the rules, the ParseTable class will need a reference to its parent ShiftReduceParser in order to query the rules. 2. In light of this, the SHiftReduceParser should be responsible for satisfying any queries the ParseTable has about rules - the ParseTable should not have to go looking & filtering the rule list held by ShiftReduceParser itself. 3. ParseTable will need a recursive method that will take a single top-level rule and recurse over it and its child rules (according to the tree I've talked about above) 4. This method in ParseTale will need to be extremely careful it doesn't get stuck in a loop. To that end, it'll have to keep track of whether it's already processed a rule or not. 5. It'll probably also have to keep track of which configurations it has added to the table class structure we defined in the last post to avoid adding rules twice. 6. Once ParseTable has figured out all the configurations and grouped them all into the right states, it will then have to recurse over the generated table and fill in all the shift / reduce / goal action(s) - not forgetting about the links to the other states they should point to. It's quite the laundry list! Thankfully, most of this is quite simple if we tackle it one step at a time. The most annoying bit is the grouping of configurations into states. This is done by looking at the token immediately before the asterisk in each configuration - all the configurations with the same token here will get grouped into the same state (while there are more complex algorithms that allow for more complex grammars, we'll stick with this for now as anything else makes my head hurt! Maybe in the future I'll look as figuring out precisely what kind of LR-style parser this is, and upgrading it to be a canonical LR(1) parser - the most advanced type I know of). This is quite a lot to take in, so I think I'll leave this post here for you to digest - and we'll get to writing some code in the next one. Found this useful? Spotted a mistake? Having trouble getting your head around it? Post a comment below! ## Shift-reduce Parser Part 1: First Steps Now that I've done the Languages and Compilers module at University, it's opened my eyes to a much better and more extensible way of handling complex text in a way that can easily be read by any subsequent code I write. To that end, I've found that at least 3 different various projects of mine could benefit from the inclusion of a shift-reduce parser, but I haven't been able to track one down for C♯ yet. With this in mind, I thought to myself: "Why not build one myself?" Sure, my Lecturer didn't go into too many details as to how they work, but it can't be that difficult, can it? Oh, I had no idea..... In this mini-series, I'm going to take you through the process of building a shift-reduce parser of your very own. As I write this, I haven't actually finished mine yet - I've just got to the important milestone of building a parse table! Thankfully, that's going to be a few posts away, as there's a fair amount of ground to cover until we get to that point. Warning: This series is not for the faint of heart! It's rather complicated, and extremely abstract - making it difficult to get your head around. I've had great difficulty getting mine around it - and ended up writing it in multiple stages. If you want to follow along, be prepared for lots of research, theory, and preparation! Let's start out by taking a look at what a shift-reduce parser does. If you haven't already, I'd recommend reading my previous compilers 101 post, which explains how to write a compiler, and the different stages involved. I'd also recommend checking out my earlier post on building a lexer, as it ties in nicely with the shift-reduce parser that we'll be building. In short, a shift-reduce parser compiles a set of BNF-style rules into a Parse Table, which it then utilises as a sort of state-machine when parsing a stream on input tokens. We'll take a look at this table compilation process in a future blog post. In this post, let's set up some data structures to help us along when we get to the compilation process in the next blog post. Here's the class structure we'll be going for: Let's start with a class to represent a single token in a rule: public enum ParserTokenClass { Terminal, NonTerminal } public struct ParserToken { public readonly ParserTokenClass Class; public readonly string Type; public ParserToken(ParserTokenClass inTokenType, string inType) { Class = inTokenType; Type = inType; } public override bool Equals(object obj) { ParserToken otherTokenType = (ParserToken)obj; return Class == otherTokenType.Class && Type == otherTokenType.Type; } public override int GetHashCode() { return$"{Class}:{Type}".GetHashCode();
}

public override string ToString()
{
string terminalDisplay = Class == ParserTokenClass.Terminal ? "T" : "NT";
return $"[ParserToken {terminalDisplay}: {Type}]"; } public static ParserToken NonTerm(string inType) { return new ParserToken(ParserTokenClass.NonTerminal, inType); } public static ParserToken Term(string inType) { return new ParserToken(ParserTokenClass.Terminal, inType); } } Pretty simple! A token in a rule can either be a terminal (basically a token straight from the lexer), or a non-terminal (a token that the parser reduces a set of other tokens into), and has a type - which we represent as a string. Unfortunately due to the complex comparisons we'll be doing later, it's a huge hassle to use an enum with a template class as I did in the lexer I built that I linked to earlier. Later on (once we've built the parse table), we'll extend this class to support attaching values and other such pieces of information to it, but for now we'll leave that out to aid simplicity. I also override Equals() and GetHashCode() in order to make comparing tokens easier later on. Overriding ToString() makes the debugging process much easier later, as we'll see in the next post! With a class to represent a token, we also need one to represent a rule. Let's create one now: public class ParserRule { /// <summary> /// A function to call when a reduce operation utilises this rule. /// </summary> public Action MatchingAction; public ParserToken LeftSide; public ParserToken[] RightSideSequence; public ParserRule(Action inMatchingAction, ParserToken inLeftSide, params ParserToken[] inRightSideSequence) { if (inLeftSide.Class != ParserTokenClass.NonTerminal) throw new ArgumentException("Error: The left-hand side must be a non-terminal token type."); MatchingAction = inMatchingAction; LeftSide = inLeftSide; RightSideSequence = inRightSideSequence; } public bool RightSideSequenceMatches(IEnumerable<ParserToken> otherRhs) { int i = 0; foreach (ParserToken nextToken in otherRhs) { if (!nextToken.Equals(RightSideSequence[i])) return false; i++; } return true; } public override string ToString() { StringBuilder result = new StringBuilder(); result.Append($"ParserRule: {LeftSide} = ");
foreach (ParserToken nextToken in RightSideSequence)
result.Append($" {nextToken}"); result.Append(";"); return result.ToString(); } } The above represents a single parser rule, such as <number> ::= <digit> <number>. Here we have the token on the left-hand-side (which we make sure is a non-terminal), and an array of tokens (which can be either terminal or non-terminal) for the right-hand-side. We also have an Action (which is basically a lamba function) that we'll call when we match against the rule, so that we have a place to hook into when we write code that actually does the tree building (not to be confused with the shift-reduce parser itself). Here I also add a method that we'll need later, which compares an array of tokens against the current rule, to see if they match - and we override ToString() here again to aid debugging. Now that we can represent tokens and rules, we can start thinking about representing configurations and states. Not sure what these are? All will be explained in the next post, don't worry :-) For now, A state can be seen as a row in the parse table, and it contains a number of configurations - which are like routes to different other states that the parser decides between, depending where it's gotten to in the token stream. public enum ParseTableAction { Shift, Reduce, Goal, Error } public class ParseTableConfiguration { public readonly ParserRule Rule; public readonly int RhsPosition; public ParseTableAction LinkingAction = ParseTableAction.Error; public ParseTableState LinkingState = null; public ParserToken TokenAfterDot { get { return Rule.RightSideSequence[RhsPosition]; } } public ParserToken TokenBeforeDot { get { return Rule.RightSideSequence[RhsPosition - 1]; } } /// <summary> /// Whether this configuration is the last in the sequence of configurations for the specified rule or not. /// </summary> /// <value><c>true</c> if is last in rule; otherwise, <c>false</c>.</value> public bool IsLastInRule { get { return RhsPosition > Rule.RightSideSequence.Length - 1; } } public ParseTableConfiguration(ParserRule inRule, int inRhsPosition) { Rule = inRule; RhsPosition = inRhsPosition; } public IEnumerable<ParserToken> GetParsedRhs() { return Rule.RightSideSequence.TakeWhile((ParserToken token, int index) => index <= RhsPosition); } public bool MatchesRhsSequence(ParserRule otherRule) { int i = 0; foreach (ParserToken nextToken in otherRule.RightSideSequence) { if (i > RhsPosition) break; if (!nextToken.Equals(otherRule.RightSideSequence[i])) return false; i++; } return true; } public override bool Equals(object obj) { ParseTableConfiguration otherConfig = obj as ParseTableConfiguration; if (otherConfig == null) return false; return Rule == otherConfig.Rule && RhsPosition == otherConfig.RhsPosition; } public override int GetHashCode() { return$"{Rule}:{RhsPosition}".GetHashCode();
}

public override string ToString()
{
StringBuilder result = new StringBuilder();

result.Append($"Configuration: {LinkingAction} "); if (LinkingState != null) result.Append($"to State {LinkingState.Id} ");
result.Append($"{Rule.LeftSide} = "); for (int i = 0; i <= Rule.RightSideSequence.Length; i++) { if (i == RhsPosition) result.Append(" * "); if (i == Rule.RightSideSequence.Length) continue; result.Append($"{Rule.RightSideSequence[i]} ");
}
result.Append(";");
return result.ToString();
}
}

This class is slightly more complicated. First, we define an enum that holds information about what the parser should do if it chooses this configuration. Then, we declare the configuration class itself. This entails specifying which parse rule we're deriving the configuration from, and both which tokens in the right-hand-side of the rule should have been parsed already, and which should still be somewhere in the token stream. Again, I'll explain this in more detail in the next post!

Then, we declare a few utility methods and properties to fetch different parts of the configuration's rule, such as the token to the immediate left and right of the right-hand-side position (which was represented as a dot . in the book I followed), all the tokens before the dot ., and whether a given rule matches this configuration in the basis of everything before the dot ..

Finally, I continue with the trend of overriding the equality checking methods and ToString(), as it makes a world of difference in the code coming up in future blog posts!

Now that we've got a class for configurations, the last one on our list is one for the states themselves. Let's do that now:

public class ParseTableState
{

public int Id {
get {
return ParentTable.FindStateId(this);
}
}

public List<ParseTableConfiguration> Configurations = new List<ParseTableConfiguration>();

public ParseTableState(ParseTable inParentTable)
{
ParentTable = inParentTable;
}

public override string ToString()
{
StringBuilder result = new StringBuilder();
foreach(ParseTableConfiguration nextConfiguration in Configurations)
result.AppendLine($" - {nextConfiguration}"); return result.ToString(); } } Much simpler than the configuration rule class, right? :P As I mentioned earlier, all a state consists of is a list of configurations in that state. In our case, we'll be assigning an id to the states in our parse table, so I include a property here that fetches a state's id from the parent parse table that it's part to make the later code as simple as possible. Still with me? Congratulations! You've got the beginnings of a shift-reduce parser. Next time, we'll expand on some of theory behind the things I've touched on in this post, and possibly look at building the start of the recursive parse table builder itself. Found this interesting? Confused about something? Comment below! ## Android app architecture: First steps and impressions This post, obviously, is not endorsed by Google or the Android Open-Source Project at all in any way. It's just my attempt to consolidate what I've learnt about it so far. I've been learning about Android development at University recently - this post is my attempt to consolidate what I've learnt. I'm by no means as confused as I have been in the past at similar stages of a module (take AI and compilers for example, though later on I figured it out). If you notice a mistake, please do let me know by posting a comment below, and I'll correct it. Note that this post isn't meant to be a complete tutorial on the subject - just to consolidate what you've already learnt (or guide your learning if you're just starting out). I'd recommend taking a course at University, or reading an tutorial on the web on the subject. Android apps, unlike a regular C or C# program, are made up of one or more activities. They don't have any particular entry point, such as the main method of a C or C# program - instead an activity is selected as the one that should be launched when the user taps the icon on their home screen. Other entry point to the app are possible too - for example services (persistent background processes) and scheduled tasks (broadcast receivers I think). Other apps can even launch your app's activities themselves! An activity is like a single screen - it's job is to perform a single, focused task. For example a contact list, or a contact details screen. When an app is launched, a new 'back stack' is created - into which new activities are inserted. It's this mechanism that makes the back button go back to the contacts list from the contact details screen when you press the back button on your phone. Activities can choose to launch an activity in a ne back stack if they want - though I think this only implies to implicit intents (more on these later) that target activities in other apps. Intents are used to instruct Android as to which child activity a parent activity would like to launch, and to carry data (serialised to a string) around between activities. There are two kinds: implicit and explicit. Explicit intents are useful when you know the exact name of the intent that you want to launch (their names are like C♯ namespaces I believe). They are most useful when you want to launch another activity that's part of your app (or an extension or your app I suppose). Implicit intents are used when you know what kind of app you want to launch, but not what it's called. Examples of this include selecting a contact from the address book, opening a URL in a web browser, and pre-filling an email or text message for the user to send. Fairly simple, right? Unfortunately, this is complicated by 2 things: a large number of Android versions (or API Versions) in use currently (I think Google are working on this long-term), and fragments. Fragments are like mini-activities. Multiple fragments can be displayed at once, and can be detached / reattached to and from the screen by way of the fragment manager. This is most useful for tablets and other devices with larger screens - An activity can dynamically fetch multiple fragments and display them at the same time. Sticking with the address book / contacts theme, on a tablet one might have the contact list down the left-hand-side of the screen, and the details of the currently selected contact down the right-hand-side of the screen. The activity is responsible for shuffling messages around between fragments (or other activities) - fragments should be completely self-contained and shouldn't be aware of other fragments that may or may not be displayed at the same time as it is. From what I can tell, the Android ecosystem has plenty of structure to it. It's (in theory) easy to put together an app even if you haven't written any Java (I can see how Java is said to be C♯'s predecessor) before - especially with the assistance that Android Studio provides, though it does feel somewhat heavy-handed and opinionated at times. I suppose any sufficiently advanced IDE carries considerable risk of being opinionated. I anticipate, going forwards, that the real problems will start to occur when I start considering compatibility between different Android API versions. Thankfully, I've got experience dealing with web browser compatibility issues, so I'm hoping that Android won't be much more problematic than that - especially since everything appears to be well-documented as to which API versions they were introduced / deprecated in. ## Compilers 101: Build your own flex + bison compiler in a few easy(?) steps So you want to build your own compiler? Great! Don't know where to start? This guide should help! At University, we're building our own compiler for a custom programming language invented by our lecturer with a pair of GNU tools by the name of flex and bison - which I've blogged about before. Since that post, I've learnt a ton about how the whole process works, so I thought I'd write up a more coherent blog post on the subject :P ### Stage 1: Planning The whole process starts with railroad diagrams (also known as flowcharts) of the language you want to write a compiler for. Having an accurate set of railroad diagrams is essential to understanding precisely how the language is put together, which is rather useful for the next step. Converting the railroad diagrams into plain BNF (Backus Naur Form). Unfortunately, bison doesn't support EBNF-like notation at the current time, so only plain-old BNF will do. ### Stage 2: Lexing With your railroad diagrams converted into BNF, you can start writing code! The first chunk of code that needs writing is the lexer. Lexing is what flex is good at - and involves converting the input source code into lexemes - discrete sequences of characters that match a particular pattern and can be assigned a particular category name, turning it into a token. Perhaps an example would help. Consider the following: void do_awesome_stuff(int a, string b) { /* Code here */ } The above can be turned into a sequence of tokens, not unlike the following (ignoring whitespace tokens, of course): TYPE: void IDENTIFIER: do_awesome_stuff OPEN_BRACKET: ( TYPE: int IDENTIFIER: a, COMMA: , TYPE: string IDENTIFIER: b CLOSE_BRACKET: ) OPEN_BRACE: { COMMENT: /* Code here */* CLOSE_BRACE: } See? We can identify 8 token types in the source string: TYPE, IDENTIFIER, COMMA, OPEN_BRACKET, CLOSE_BRACKET, OPEN_BRACE, COMMENT, and CLOSE_BRACE. These types and the rules to match them can be found by analysing a combination of the railroad diagrams and the BNF you created earlier. ### Stage 3: Parser the first With a lexer in hand, we can now look at writing the parser. This is done in two stages. The parser itself, and upgrading said parser to generate a parse tree. Let's talk about the parser first. The parser can be largely created simply by running a few regular-expression find and replace rules on your BNF, actually. From there, it's just a case of adding the header and the footer to complete the document. Let's take a look at some example BNF: <instructions> ::= START <lines> END <lines> ::= <lines> <line> | <line> <line> ::= <command> <command> ::= <cmd_name> <number> <cmd_name> ::= FD | BK | LT | RT <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 The above matches something like the following: START FD 100 RT 180 FD 125 LT 90 BK 50 END Very interesting (a virtual cookie is available for anyone who gets the reference as to what this grammar represents!). Let's look at converting that into something bison can understand: instructions : START lines END ; lines : lines line | line ; line : command ; command : cmd_name number ; cmd_name : FD | BK | LT | RT ; number : number digit | digit ; digit : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 That's looking much better already! Simply by using the regular expression substitutions: 1. <([a-z_]+)> -> $1
2. ::= -> :
3. \n\n -> \n\t;\n\n

....we can get most of the way there to something that bison can understand. Next, we need to refactor it a bit to tell it which tokens are coming from the lexer (which I'll leave up to you to write as an exercise), so it doesn't get them confused with the rules - which are defined in the BNF(-like) rules.

Let's get rid of the rule for number and digit first, since we can do those in the lexer quite easily. Next, let's add a %token definition to the top to tell it which are coming from the lexer. It's good practice to define everything that comes from the lexer in uppercase, and everything that's a rule that exists only in bison in lowercase:

%start instructions
%token FD BK LT RT NUMBER START END

We've also defined a start symbol - the one which when bison reaches it, it knows that it's completed the parsing process, as bison is a bottom-up parser.

Lastly, we need to reference the lexer itself. Thankfully that's easy too by appending to your new bison file:

%%

#include "lex.yy.c"


Very nice. Don't forget about the new line at the end of the file - flex and bison will complain if it isn't present! Here's the completed bison file:

%start instructions
%token FD BK LT RT NUMBER START END

instructions : START lines END
;

lines : lines line
| line
;

line : command
;

command : cmd_name NUMBER
;

cmd_name : FD
| BK
| LT
| RT
;

%%

#include "lex.yy.c"


With a brand-new bison file completed, there's just one component of the parser left - a plain-old C file that calls it. Let's create one of those quickly:


#include

int yyparse(void);

int main(void)
{
# if YYDEBUG == 1
extern int yydebug;
yydebug = 1;
#endif

return yyparse();
}

void yyerror(char *error_message)
{
fprintf(stderr, "Error: %s\nExiting\n", error_message);
}


The highlighted lines enable a special debugging mode built-in to bison if the standard compile-time symbol YYDEBUG is specified - and bison is run with a few special parameters. Here's the sequence of commands needed to compile this:

flex lexer.l
bison -tv parser.y
gcc -Wall -Wextra -g parser.tab.c main.c -lfl -ly -DYYDEBUG -D_XOPEN_SOURCE=700

The gcc command is probably a bit long-winded, but it does several useful things for us:

• Shows additional warnings just in case we've made a mistake that might be an issue later (-Wall -Wextra)
• Include additional debugging information in the output file to allow debugging with gdb (the GNU Debugger) if necessary (-g)
• Fix strange errors on some systems (-D_XOPEN_SOURCE=700)

If you're on a Windows system, you may need to remove the -ly - which appears to be required on the Linux machines I use - it tells gcc that we'll be referencing the bison library.

### Stage 4: Parser again

Congratulations on getting this far! You've now got a lexer and a parser - so it's time to put them to use. This is done by utilising the parser to build a parse tree - a tree of nodes that represent the input. Here's an example tree:

As you can see, each high-level node references one or more lower-level nodes, and the structure of the tree represents the first 2 lines of the example input above. The nodes in yellow are lexical tokens that come directly from flex - these are called terminals, or leaf nodes. The ones in purple come from the bison rules (which we derived from the BNF we wrote at the beginning of this post) - and are non-terminals, or tree nodes.

With this in mind, let's introduce another feature or two of bison. Firstly, let's take a look at revising that %token declaration we created above:

%token FD BK LT RT START END
%token<val_num> NUMBER

The important bit here is the <val_num>. Here we tell bison that a value should be attached to the token NUMBER - and that it will be of type int. After telling bison that it should expect a value, we need to give it a place to put it. Let's write some more code to go just below the %token declarations:

%union {
int val_num;
}

There we go! Excellent - we've got a place to put it. Now we just need to alter the lexer to convert the token value to an int and put it there. That's not too tough, thankfully - but if you're having trouble with it, here's a hint:

{number}        { yylval.val_num = atoi(yytext); return(NUMBER); }

Now we have it passing numbers correctly, let's look briefly at generating that parse tree. I'm not going to give the game away - just a few helpful hints as to what you need to do here - otherwise it's not as fun :P

Generating the parse tree can be considered the both the most challenging part of the experience (especially if you don't know what you're doing) and the easiest to deal with at same time. Knowing your stuff and your end goal before you start makes the whole process a lot easier.

The first major step is to create a struct that can represent a type of node in your parse tree. It might be useful to store several properties here - such as the node type (An enum will come in handy here), a spot for the value of a lexical token (or a reference to it in a symbol table if you have one), and references to child nodes in the parse tree.

The second major step of the process is to create a utility method that creates a new node of the tree on the heap, and then revise the bison file to get each rule to create new nodes on the tree in such a way that it creates a parse tree when it reaches start node (or top node of the tree - which, in the case of the above, is instructions). For the purposes of this post, I'll be using a method with this prototype:

TreeNode create_node(int item, int node_type, TreeNode left, TreeNode right);

Your tree node struct and subsequent creation method may vary. With this in hand, we can revise the bison rules we created above to create these nodes we've been talking about. Here's a quick pointer on how to revise the rule for command above:

command : cmd_name NUMBER   { $$= create_node(2, NODE_COMMAND, 1, NULL); } ; This might look a bit strange, but let's break it down. The bit in curly braces is some (almost) plain C code that creates the node and returns a pointer to it to bison. The $$ is the return value for that node - which, I might add reminds me of something I forgot above. We need to tell bison about our new tree node data type and which rules should return it:

%type<val_tnode> instructions lines line command cmd_name

/* And in %union { ... } ..... */
TreeNode val_tnode;

This is almost the same as the %token<val_num> we did before, but we're defining the return value of a rule this type - not a token. With that little interlude out of the way, let's return to the code above. $1 and $2 refer to the first and second items in the rule definition respectively - and hold the type that we defined above in the %token and %type directives. Since bison is a bottom-up parser - this means that by the time this code executes, all it's child nodes have (hopefully) been created - and we just have to tie them all up together with a new node. In the case of my little example above, $1 is of type TreeNode, and $2 is of type int (that is if I didn't make any mistakes further up!).

### Stage 5: Blasting off to code generation and beyond

Phew! That's a lot of work. If you've read this far, thank you and well done! It's been a long journey for both you the reader and me the writer, but you're almost done.

While conceptually simple when broken down, the whole process actually gets rather involved - especially when writing the BNF and the parser (the latter of which can be a particular pain due to shift/reduce and reduce/reduce errors), and the amount of code and head scratching you've got to do to get to this point is enormous. My best advice is to take it slow and don't rush - you'll only cause most problems for yourself if you try and jump the gun. Make sure that each stage works as you intend before you continue - back-pedalling to fix an issue can be particularly annoying as it can be bothersome to work out which stage the bug is actually in.

The last step of the whole process is to actually do something with the parse tree we've worked so hard to create. Thankfully, that's not too difficult - as we can put some additional code in the { } block of the starting symbol to call methods that will do things like perform some optimisation, print the tree to the console - or generate some sweet code. While the actual generation of code is beyond the scope of this article, I may end up posting about some optimisation techniques you can use on a parse tree after I've finished fiddling with float handling, symbol tables, and initial code generation in my ACW (Assessed Course Work).

Found this useful? Found a bug in this post? Got a suggestion? Comment below! Since I don't have any real analytics on this blog besides the server logs, I've no idea if you've read it really unless you comment :P