In this problem-series, you're to implement a subset of the Lua language (version 5.1), called mini-lua (mua). This is one of Rujia Liu's experimental languages, mainly for implementing algorithms, not real-world programs.
This is the second problem in the series, which requires you to write an expression evaluator. The grammar below is described in extended BNF, in which {x} means "x appears one or more times", [x] means "x appears 0 or 1 time", and x | y means "either x or y (but not both) appear exactly 1 time".
mini-lua is a dynamically typed language. This means that variables do not have types; only values do. There are no type definitions in the language. All values carry their own type.
There are six basic types in Lua: nil, boolean, number, string, function, table.
Tables and functions values are objects: variables do not actually contain these values, only references to them. Assignment, parameter passing, and function returns always manipulate references to such values; these operations do not imply any kind of copy.
To lua programmers: Lua has two more basic types: userdata and thread, both are not supported in Mini-Lua. Mini-lua has very limited support for FP (functional programming). For example, lambda expression is not supported, and you cannot return a function or closure in a function.
A variable defined as follows:
var -> NAME { `.' NAME | `[' expr `]' }
Here "expr" means any valid expression, because tables can be indexed with any value. Note that the "dot" syntax is a syntactic sugar that makes the expression "look like accessing object member". For example, a.name is equivalent to a["name"].
Variables have values of nil by default. If you assignment nil to a variable, you're removing that variable. Similarly, you can assign a nil to an element in a table to remove it from the table.
To lua programmers: Lua provides more syntactic sugars, NAME `:' NAME args. Let's ignore these.
An expression consists of so-called "simple expressions":
simpleexp -> NUMBER | STRING | nil | true | false | `{' '}' | var | functioncallHere `{' '}' means an empty table.
To lua programmers: Lua provides more convenient ways to construct tables. However, they add complexity to the language so we don't use them. Moreover, mini-lua does not support lambda expressions.
The functioncall expression in the last section is defined this way:
functioncall -> var `(' [ expr {`,' expr } ] `)'
To lua programmers: In mini-lua, the only way to call a function is directly specifying the variable holding that function. For example (print)(1) won't work, but a = (f) is allowed, because (f) is a valid expression (see below). In Lua, if you call a function with a string constant or table constructor, the parenthesis' could be omitted. This syntax is not supported in mini-lua.
Now we have all the building blocks. We use operators to combine simple expressions into complex expressions (i.e. "expr"):
expr -> simpleexp | expr binop expr | unop expr | `(' expr `)'
Note that this grammar does not consider operator precedence's, which is summarized in the following table (from low to high):
or and < > <= >= ~= == .. + - * / % not # - (unary) ^
Most of them are common-sense, but there are several things to mention:
To lua programmers: In lua, concatenation is right associative (See: http://lua-users.org/wiki/AssociativityOfConcatenation), but for this problem, whether it is left or right associative doesn't affect the result. Morever, "and" and "or" do not always return boolean values in Lua, but we restrict the result to boolean values in mini-lua in order to simplify the language. Maybe the most import change is: No automatic conversions between strings and numbers (i.e. no coercion).
For testing purpose, here are some functions you should implement (extracted from Lua 5.1 manual, with simplifications):
Tries to convert its argument to a number. If the argument is already a number or a string convertible to a number, then tonumber returns this number; otherwise, it returns nil. Note that there is no optional parameter as in Lua.
Receives an argument of any type and converts it to a string in a reasonable format. In mini-lua, if e is a function or a table, return "function" or "table" instead. If e is a number, convert it to a string using the traditional C format string "%.14g" (it's the default format string in lua 5.1, see luaconf.h). Don't worry you're using other programming languages and do not know the exact semantics of the format string, you can choose your own way. We're not testing the strict format in the judge data.
Prints tostring(e) to standard output, followed by a newline. Note that in mini-lua, this function can only print one value.
Returns a string that is the concatenation of n copies of the string s.
Returns the substring of s that starts at i and continues until j; i and j can be negative. If j is absent, then it is assumed to be equal to -1 (which is the same as the string length). In particular, the call string.sub(s,1,j) returns a prefix of s with length j, and string.sub(s, -i) returns a suffix of s with length i.
Given an array where all elements are strings, returns table[1]..table[2].. ... table[#table]. The default value for sep is the empty string.
Sorts table elements in a given order, in-place, from table[1] to table[n], where n is the length of the table. If comp is given, then it must be a function that receives two table elements, and returns true when the first is less than the second (so that no comp(a[i+1],a[i]) will be true after the sort). If comp is not given, then the standard operator < is used instead. Note that the sort algorithm is not stable, but we're carefully designing the test data so that how the sort is implemented does not affect the final.
Returns the absolute value of x, the largest integer smaller than or equal to x, and the smallest integer larger than or equal to x, respectively.
Returns the square root of x, the value ex, ln(x) and log10(x).
math.pi is a variable holding the value of pi, while the other two functions converts between degrees and radians.
Returns the value of math functions, in radians.
Returns the value of math functions, assuming x is in radians.
Returns the smaller/larger value of x and y.
There will be multiple mini-lua programs. Each program consists of lines. Each line is either in the form print(expr), or in the form var = expr (indicates an assignment). All the expressions will obey the rules above. An empty line terminates a program (all the variables should be reset to nil). The expressions will be correct and evaluates to a reasonable value (for example, you don't have to handle NaN or arithmetic overflows, and you will not be asked to compare a number with a string). We will not re-assign these functions/variables, though we may assign them to new variables. There will be no comments in the program.
For each line in the form print(expr), print the expression. When printing numbers, print as many digits as you like, as long as the relative error OR the absolute error is no more than 1e-9.
print(1+2*3/4) f = math.sin print(f(1.57)) print(1<2 and 4+5==9) print(math.max(3,-math.min(5*7,-4))) a={} a[1]={} a[1][2]={} a[1][3]="hehe\'\\" a[1][1]=a print(#a) print(#a[1]) print(#a[1][3]) print(a) print(f) print(a[1][1][1][3] .. "\n" .. "..")
2.5 0.99999968293183 true 4 1 3 6 table function hehe'\ ..