Yueliang

Introduction

The goal of Yueliang is to implement Lua 5 in Lua 5. Such a codebase, if well documented, can be a useful prototyping and educational tool. Initially, the focus is on the front end of Lua, i.e. the lexical analyzer, the parser and the code generator, in order to generate binary chunks. A port of the back end (the VM) is being considered. Yueliang is moon in Mandarin.

The codebase is currently a no-brainer port of the Lua 5.0.3 front end and the Lua 5.1.3 front end. C source code was ported to Lua code in a brain dead manner, and the C heritage is retained as much as possible to allow for easy comparison. Due to certain implementation methods, processing might be slow (especially if the source file causes a lot of string processing.) The initial version is not meant to be fast. Even unused arguments are retained. Asserts are currently enabled. While the Lua code itself is portable, portions of the code is hard-coded to generate output for an x86-type platform (32-bit ints, doubles, little-endian.)

There is an automatic tester script to exercise the front end. Both the lexer and the parser have test suites, for both front end versions. There isn't any test suite for a back end yet because the back end is currently being ported, but much of Lua's test suite can be utilized for that. Yueliang currently produces the exact binary chunk as the original Lua 5 itself for hundreds of KB of various Lua scripts that I have on my machine. Performance (not currently a consideration) is 28 seconds on an Athlon 2500+, or about 29.5KB/sec, for Yueliang 0.1.0. (Native C is virtually instantaneous, so a comparison is pointless, really.)

Features

Yueliang includes the following:

• Lua 5.0.3 material:
  
• a working front end, generates binary chunks
  
• a test suite for the lexer, with about 60 pass/fail cases
• a test suite for the parser, with 503 pass/fail cases
  
• experimental native lexers (working and tested)
  
• an experimental native parser skeleton (working and tested)
• sample call tree log files showing how grammar is parsed
  
• Lua 5.1.3 material:
  
• a working front end, generates binary chunks
• a test suite for the lexer, with about 60 pass/fail cases
  
• a test suite for the parser, with 524 pass/fail cases
• an experimental native lexer (working and tested)
• an experimental native parser skeleton (working and tested)
• sample call tree log files showing how grammar is parsed
• Miscellaneous:
  
• a lexer benchmarking script (5.0.x only)
  
• IEEE double conversion functions and tests
• a call graph trace utility for studying the parser and code generator
• an interactive 5.0.x expression parsing demo

Users of Yueliang

A practical use of Yueliang's native 5.1.x parser skeleton is in LuaSrcDiet version 0.11.0, for the powerful local variable renaming feature. The native parser skeleton is used to provide a table of local and global variable "liveness", or in detail, when they are declared, activated, accessed or removed. The parser behaves in exactly the same way as a normal Lua front end. This allows LuaSrcDiet to reassign local variable names in a general way, including dealing with upvalue accesses and renaming function parameters. Furthermore, by avoiding name collisions, short names can be reused more often, possibly further reducing code size for large scripts.

Portions of Yueliang is also used in Metalua.

Download

Project Links on LuaForge: Yueliang project page | File releases

Latest version: yueliang-0.4.1 (170KB tar.gz)

What's new?

• 2008-05-31 [0.4.1]:
• Tested native 5.0.x and 5.1.x parsers with lots of test cases.
• Fixed two bugs in native 5.1.x parser, # and % operator handling.
  
• 2008-05-22 [0.4.0]:
• A working native parser skeleton for Lua 5.1.x, plus code to deal with variable classification.
• Sample parser log files covering all of the grammar, plus some variable classification testing.
  
• 2008-05-20 [0.3.2]:
• A working native lexer for Lua 5.1.x.
  
• 2008-05-19 [0.3.1]:
• Mark 2 of the native parser skeleton for 5.0.3, does variable classification into locals, upvalues or globals.
  
• Sample parser log files generated by the Mark 2 5.0.3 parser skeleton exercising variable classification.
• 2008-04-13 [0.3.0]:
• Native parser skeleton for 5.0.3 mostly works. Not exhaustively tested, though.
  
• Sample parser log files generated by the 5.0.3 parser skeleton covering all of the grammar.
  
• 2008-04-12 [0.2.4]:
• New partially working native parser skeleton for 5.0.3. Prints logged messages of parsing operations.
  
• 2008-04-09 [0.2.3]:
• Bumped 5.1.x front end code to Lua 5.1.3
• 2007-11-22 [0.2.2]:
• Bumped 5.1.x front end code to Lua 5.1.2
  
• 2006-11-28 [0.2.1]:
• Added parser test suites for both 5.0.3 and 5.1.1 front ends
• One bug fixed for the 5.1.1 front end (non-vararg function allowed dots in body)
  
• 2006-11-22 [0.2.0]:
• 5.1.1 front end now operational, tested and binary chunks are generated correctly
  
• 2006-11-18 [0.1.4]:
• updated 5.0.2 material to 5.0.3, updated front end test script
• updated 5.1 material to 5.1.1, added ldump.lua, lopcodes.lua, and some test scripts, lexer debugged
  
• 2006-11-11 [0.1.3]:
• added a Lua-style expression parsing demonstrator
• started work on Lua 5.1 equivalent, added a Lua 5.1 lexer
• added comments for 5.0.2 parser
• wrote native versions of the 5.0.2 lexer that are smaller and faster
• this will be the last 5.0.2 release before 5.0.2 files are updated to 5.0.3
  
• 2005-04-18 [0.1.2]:
  
• added test cases for number conversion functions in ldump.lua (recognizes +/- infinity now)
• 2005-03-21 [0.1.1]:
  
• added a script to generate a call graph or hierarchy
• 2005-03-17 [0.1.0]:
  
• initial release: lexer/parser/code generator works, and binary chunks can be produced

Current work being done:

• Concise parser skeletons (done for both 5.0.3 and 5.1.x, no further work for 5.0.3).
• Code generation written in native Lua (to be done for 5.1.x code base only).
  
• Port the 5.1.x virtual machine over to Lua (on hiatus, need to finish second item first).
• Write educational tools to learn the front end (ongoing in the process of writing native parsers).

Acknowledgements

Thanks to the LuaForge team for hosting this material. This page was written on SeaMonkey. Yueliang was developed using the SciTE editor on Cygwin, and managed using SVN. Much of Yueliang is based on the Lua sources.