My Experience with Some Parser Generators

TOML is a new data format (and young) standard that can hold information similar to JSON and YAML. TOML wants to be simple to write, use and implement. Thanks to those goals and a need for a data format for my games, I thought I’d take a whack at implementing it myself in C.

My formal computer science education and my ever continuing interest in programming languages has taught me about language grammars and parsing. Though I’ve never used the ideas and theories actively in something complete and useful. I didn’t go as far as writing the parser from scratch. Not this time. Instead I ended up using tools called Lemon and re2c to make tomlc.

I didn’t intend to try multiple parser generators. At first look I thought ANTLR would do what I wanted and needed but due to issues I couldn’t make it work. Bison and Flex was my next shot but I found certain limitations to make it undesirable for this implementation. I finally landed with Lemon that while the grammar file, I think, is more complicated it works brilliantly. I found each of the generators to be great and given certain project details they could each be workable.

ANTLR

ANTLR is pretty fantastic. My suspicion is that it’ll generally work better with vm languages than it did for me with C. An external runtime library is needed for C for ANTLR3. I spent some hours tracking down documentation for ANTLR and the C library, some more trying to debug the seg faults that appeared in the antlr runtime library and some final time looking through the library’s source. In the end I figure I was mismatching the runtime library with the version of antlr to generate the C code. Just not making enough progress with the time I spent I moved on to the next parser generator.

While ANTLR didn’t work for me, it definitely has some cool benefits. Compared to the later generators the grammar was simpler to write. Other parser generators rely on a separate method to lexically scan tokens from the input, ANTLR has that built into the grammar files. If you are using the older version 3 than the more recent version 4, as I did since it does not yet support a C target, you can target a number of languages instead of version 4’s two current targets.

Here is what my resulting ANTLR grammar was before I moved to the next generator:

I can’t guarentee that this is an accurate grammar for TOML and it’s definitely incomplete, just that ANTLR3 builds target parsers with it.

ATF / Kyua

Since this was a project that was partly about trying things I hadn’t before experimented with unit test libraries. Seeing a lot of mentions for ATF, Automated Testing Framework, now known as Kyua, pronouced QA, I gave that a try. It has a lot of great features and an approach that could be useful for debugging users that made it very enticing. But I ended up running into a really big problem building Kyua’s developer tool. The library built easily but oddly the tool to run the built test suites created enough 450 meg core dumps as it built to fill all the free space on my computer’s drive. I succeeded at building it eventually but being frustrated at building Kyua and not wanting to explain how to work around the core dump issue in docs for my library, I gave up on it. The start of this project was rather frustrating.

Bison

Next on the list. Bison. An implementation of Yacc. I didn’t try it for as long as ANTLR. I made a simple TOML grammar and lexer with Flex that would compile. Poking through the generated source and figuring out how to build around it with the created APIs alerted me to the global variables Bison uses. Bison’s C++ version supports being executed in multiple threads but not the C output. Though it could be used fine, starting fresh with this parser, maybe I step further. So I started peaking around other generators that could support threaded parsing.

Oh yeah, the simple Bison grammar and Flex lexer.

Lemon

Lemon, maintained by sqlite, builds on the ideas of Bison and Yacc. It definitely has some positives going for it. On the downside it uses a grammar style that can be harder to work with. While its documentation is shorter than the above mentioned generators, I found the content to bring me up to speed quicker than the others.

Lemon’s constraints and modifications grammatically really do make it simpler to use. Specifying names for a grammar rule’s components is really nice to have instead of counting which argument has the token you want to work on.

As designed, Lemon also doesn’t allow terminal tokens to be written in its grammar. Instead Lemon strictly has you provide a lexer to break string content into tokens for the generated parser to consume. Part of this clean separation of functionality also allows me to have lots of control in what to use to lexically analyze the input.

While ANTLR does everything itself, Yacc, Bison, and Lemon require a second tool to tokenize the input. Lemon’s provided freedom in this really leaves you open. Fortunately some other online posts mentioned re2c. As well both Lemon and re2c leave you to define how to communicate between the parts. At minimum you need to pass an integer to indicate the token type. But to be useful you’ll probably pass the string content of the token.

One thing odd about Lemon, it doesn’t have a way to write output files to a target directory from the tool.

To finish up about parser generators, my final Lemon grammar.

Unless I am forgetting something, this is a complete grammar for TOML. Paired with my re2c powered tokenizer, the above grammar can make sense of a TOML document.

Oh Yeah, Other Testing Stuff

I tried fctx and ended using libtap for testing. Compared to Kyua that are greatly lacking in features but I also found those attractive. However fctx and libtap are so simple it’s hard to screw up using or compiling them. libtap is a step simpler and writes test results in TAP. In the end, that last bit and being simple to use were my deciding factors for the test suite’s library.

Play SpaceLeap
Space Leap is a game of exploration and collection and about loneliness. It was first made for iamagamer Jam back in July. After my last many jam games over the last two years I’ve postmortem-ed at most a week after. This one has taken 5 months to get to.
The first version of SpaceLeap let you jump around, collect one resource, and turn it into oxygen, the life sustaining resource that lets you continue to play a run in the game. It was a simple game jam game. I got to improve my engine with it. My favorite element I worked on in the first SpaceLeap version over that weekend was the writing. Not the words, grammar, or voice, but that I had words there, telling any kind of story.
The iamagamer jam in July was about making games with female protagonists. I thought about what makes a game about female protagonists leading up to the jam. A lot of other games and media bug me with characters that indicate a female character’s gender with cultural female signifiers. Something Anita Sarkessian discussed really well recently. Being a woman doesn’t define a character, it is an element among many of who they are. This can be told by the characters visual design, especially if tropes are avoided, but also the story of who they are.
Past jams didn’t challenge me with something I thought I should respond by writing an actual in-game story. That really excited me leading up to this one. It’s what excites me about continuing to work on SpaceLeap. What I wrote for the original version and what is mostly there unchanged, I don’t think it is enough. I want to write more story and will.
Since the first version I edited one tiny part of the story and have been instead working on systems to add sound, and getting terribly distracted by that, and more recently how the character moves. The character has two forms of movement, jumping and object movement. Jumping is simple and straight forward, unchanged except for speed. Moving though, while on a body though was mostly a hack using the same login for jumping.
Instead of that hacky motion, I wanted something that felt nice but distinctively quirky. A rolling stroll. Bouncing. The overall idea is that the player’s vehicle is like a lunar lander and impacter mixed together. The movement on these astral bodies is regular and steady and controllable. Launching into the mysterious void is controllable at the beginning but then your floating at the whims of this game’s universe.
The new version improves on the body movement. Instead of jerkily throwing the vehicle into body, it now rolls around. Stepping and stopping around. For a bit I had a stage in-between rolling around a body and launching but this was really confusing to people who play tested it for me. The rolling is odd but the awkward movement is appropriate.
SpaceLeap is about loneliness. The story, the physics, the environment, talks about this. The story says you’re specifically here alone. The physics movement around a body is awkward, in part because I personally like the style for this game, but in an artsy sense it reflects an awkwardness of the character. Jumping into the environmental void you can’t see your destination, in another artsy sense, new friends, until you run into them.
I didn’t intend to make a game about loneliness but it is something I’m well acquainted with. I attended three different elementary schools as my parents moved my family around a lot. Once my family settled for the last 10 years of my childhood, we lived only near one family that we became very well acquainted with. All of my other later childhood friends lived 10 to 25 miles away. Living so far away meant I couldn’t regularly hang out with friends until 10th grade when I had a drivers license. Marching band though is probably why I didn’t end up a friendless loner.
Space Leap isn’t supposed to be a sad game. Just one where the character grows in a lonely environment.
Space Leap is finally somewhere where I’m happy to write about it. While I’m next immediately working on early sound and music, improving Space Leap with further game mechanics and more story points, than at the start and end of the game currently, is something I’ll be working on during and after the next iteration.
Play SpaceLeap

Play SpaceLeap

Space Leap is a game of exploration and collection and about loneliness. It was first made for iamagamer Jam back in July. After my last many jam games over the last two years I’ve postmortem-ed at most a week after. This one has taken 5 months to get to.

The first version of SpaceLeap let you jump around, collect one resource, and turn it into oxygen, the life sustaining resource that lets you continue to play a run in the game. It was a simple game jam game. I got to improve my engine with it. My favorite element I worked on in the first SpaceLeap version over that weekend was the writing. Not the words, grammar, or voice, but that I had words there, telling any kind of story.

The iamagamer jam in July was about making games with female protagonists. I thought about what makes a game about female protagonists leading up to the jam. A lot of other games and media bug me with characters that indicate a female character’s gender with cultural female signifiers. Something Anita Sarkessian discussed really well recently. Being a woman doesn’t define a character, it is an element among many of who they are. This can be told by the characters visual design, especially if tropes are avoided, but also the story of who they are.

Past jams didn’t challenge me with something I thought I should respond by writing an actual in-game story. That really excited me leading up to this one. It’s what excites me about continuing to work on SpaceLeap. What I wrote for the original version and what is mostly there unchanged, I don’t think it is enough. I want to write more story and will.

Since the first version I edited one tiny part of the story and have been instead working on systems to add sound, and getting terribly distracted by that, and more recently how the character moves. The character has two forms of movement, jumping and object movement. Jumping is simple and straight forward, unchanged except for speed. Moving though, while on a body though was mostly a hack using the same login for jumping.

Instead of that hacky motion, I wanted something that felt nice but distinctively quirky. A rolling stroll. Bouncing. The overall idea is that the player’s vehicle is like a lunar lander and impacter mixed together. The movement on these astral bodies is regular and steady and controllable. Launching into the mysterious void is controllable at the beginning but then your floating at the whims of this game’s universe.

The new version improves on the body movement. Instead of jerkily throwing the vehicle into body, it now rolls around. Stepping and stopping around. For a bit I had a stage in-between rolling around a body and launching but this was really confusing to people who play tested it for me. The rolling is odd but the awkward movement is appropriate.

SpaceLeap is about loneliness. The story, the physics, the environment, talks about this. The story says you’re specifically here alone. The physics movement around a body is awkward, in part because I personally like the style for this game, but in an artsy sense it reflects an awkwardness of the character. Jumping into the environmental void you can’t see your destination, in another artsy sense, new friends, until you run into them.

I didn’t intend to make a game about loneliness but it is something I’m well acquainted with. I attended three different elementary schools as my parents moved my family around a lot. Once my family settled for the last 10 years of my childhood, we lived only near one family that we became very well acquainted with. All of my other later childhood friends lived 10 to 25 miles away. Living so far away meant I couldn’t regularly hang out with friends until 10th grade when I had a drivers license. Marching band though is probably why I didn’t end up a friendless loner.

Space Leap isn’t supposed to be a sad game. Just one where the character grows in a lonely environment.

Space Leap is finally somewhere where I’m happy to write about it. While I’m next immediately working on early sound and music, improving Space Leap with further game mechanics and more story points, than at the start and end of the game currently, is something I’ll be working on during and after the next iteration.

Play SpaceLeap

(1) President Abraham Lincoln, who had depression
(2) Writer Virginia Woolf, who had bipolar disorder
(3) Artist Vincent Van Gogh, who had bipolar disorder
(4) Writer Sylvia Plath, who had depression
(5) Mathematician John Nash (from A Brilliant Mind), who had schizophrenia

Inspired by this post

(Source: madvocate)

itsalltemporary:

blackquarterasian:

theomeganerd:

Pokemon Pokecenter Imagined in Modern 3D by Evan Liaw

angrydinosaur:

Amazing.

A depth of awesome info.

myrntai:

Indian ink, Copics and background in Photoshop.

myrntai:

Indian ink, Copics and background in Photoshop.

Sprites for a Global Game Jam 2013 game about robots with hearts that you program to maintain a building. Beep beep BEEP.
Theme: Sound of a Heartbeat.

Sprites for a Global Game Jam 2013 game about robots with hearts that you program to maintain a building. Beep beep BEEP.

Theme: Sound of a Heartbeat.

“You know in 1993 we weren’t the bicycling capital of America. Seventeen years later, for the equivalent cost of a single mile of freeway, we have a bike infrastructure.”
Sam Adams, Mayor of Portland, Oregon; where ~8% of commuters cycle to work. (via tasfromtas)

im-cool-like-that:

The World’s Smallest Dog x

A wild Lillipup appears!