Merge change 3514 into donut
* changes:
core of edify, an eventual replacement for amend
diff --git a/edify/Android.mk b/edify/Android.mk
new file mode 100644
index 0000000..803fba2
--- /dev/null
+++ b/edify/Android.mk
@@ -0,0 +1,40 @@
+# Copyright 2009 The Android Open Source Project
+
+LOCAL_PATH := $(call my-dir)
+
+edify_src_files := \
+ lexer.l \
+ parser.y \
+ expr.c
+
+# "-x c" forces the lex/yacc files to be compiled as c;
+# the build system otherwise forces them to be c++.
+edify_cflags := -x c
+
+#
+# Build the host-side command line tool
+#
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := \
+ $(edify_src_files) \
+ main.c
+
+LOCAL_CFLAGS := $(edify_cflags) -g -O0
+LOCAL_MODULE := edify
+LOCAL_YACCFLAGS := -v
+
+include $(BUILD_HOST_EXECUTABLE)
+
+# #
+# # Build the device-side library
+# #
+# include $(CLEAR_VARS)
+
+# LOCAL_SRC_FILES := $(edify_src_files)
+# LOCAL_SRC_FILES += $(edify_test_files)
+
+# LOCAL_CFLAGS := $(edify_cflags)
+# LOCAL_MODULE := libedify
+
+# include $(BUILD_STATIC_LIBRARY)
diff --git a/edify/README b/edify/README
new file mode 100644
index 0000000..5ccb582
--- /dev/null
+++ b/edify/README
@@ -0,0 +1,108 @@
+Update scripts (from donut onwards) are written in a new little
+scripting language ("edify") that is superficially somewhat similar to
+the old one ("amend"). This is a brief overview of the new language.
+
+- The entire script is a single expression.
+
+- All expressions are string-valued.
+
+- String literals appear in double quotes. \n, \t, \", and \\ are
+ understood, as are hexadecimal escapes like \x4a.
+
+- String literals consisting of only letters, numbers, colons,
+ underscores, and slashes don't need to be in double quotes.
+
+- The following words are reserved:
+
+ if then else endif
+
+ They have special meaning when unquoted. (In quotes, they are just
+ string literals.)
+
+- When used as a boolean, the empty string is "false" and all other
+ strings are "true".
+
+- All functions are actually macros (in the Lisp sense); the body of
+ the function can control which (if any) of the arguments are
+ evaluated. This means that functions can act as control
+ structures.
+
+- Operators (like "&&" and "||") are just syntactic sugar for builtin
+ functions, so they can act as control structures as well.
+
+- ";" is a binary operator; evaluating it just means to first evaluate
+ the left side, then the right. It can also appear after any
+ expression.
+
+- Comments start with "#" and run to the end of the line.
+
+
+
+Some examples:
+
+- There's no distinction between quoted and unquoted strings; the
+ quotes are only needed if you want characters like whitespace to
+ appear in the string. The following expressions all evaluate to the
+ same string.
+
+ "a b"
+ a + " " + b
+ "a" + " " + "b"
+ "a\x20b"
+ a + "\x20b"
+ concat(a, " ", "b")
+ "concat"(a, " ", "b")
+
+ As shown in the last example, function names are just strings,
+ too. They must be string *literals*, however. This is not legal:
+
+ ("con" + "cat")(a, " ", b) # syntax error!
+
+
+- The ifelse() builtin takes three arguments: it evaluates exactly
+ one of the second and third, depending on whether the first one is
+ true. There is also some syntactic sugar to make expressions that
+ look like if/else statements:
+
+ # these are all equivalent
+ ifelse(something(), "yes", "no")
+ if something() then yes else no endif
+ if something() then "yes" else "no" endif
+
+ The else part is optional.
+
+ if something() then "yes" endif # if something() is false,
+ # evaluates to false
+
+ ifelse(condition(), "", abort()) # abort() only called if
+ # condition() is false
+
+ The last example is equivalent to:
+
+ assert(condition())
+
+
+- The && and || operators can be used similarly; they evaluate their
+ second argument only if it's needed to determine the truth of the
+ expression. Their value is the value of the last-evaluated
+ argument:
+
+ file_exists("/data/system/bad") && delete("/data/system/bad")
+
+ file_exists("/data/system/missing") || create("/data/system/missing")
+
+ get_it() || "xxx" # returns value of get_it() if that value is
+ # true, otherwise returns "xxx"
+
+
+- The purpose of ";" is to simulate imperative statements, of course,
+ but the operator can be used anywhere. Its value is the value of
+ its right side:
+
+ concat(a;b;c, d, e;f) # evaluates to "cdf"
+
+ A more useful example might be something like:
+
+ ifelse(condition(),
+ (first_step(); second_step();), # second ; is optional
+ alternative_procedure())
diff --git a/edify/expr.c b/edify/expr.c
new file mode 100644
index 0000000..b3b8927
--- /dev/null
+++ b/edify/expr.c
@@ -0,0 +1,279 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <string.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdarg.h>
+
+#include "expr.h"
+
+// Functions should:
+//
+// - return a malloc()'d string
+// - if Evaluate() on any argument returns NULL, return NULL.
+
+int BooleanString(const char* s) {
+ return s[0] != '\0';
+}
+
+char* Evaluate(void* cookie, Expr* expr) {
+ return expr->fn(expr->name, cookie, expr->argc, expr->argv);
+}
+
+char* ConcatFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ if (argc == 0) {
+ return strdup("");
+ }
+ char** strings = malloc(argc * sizeof(char*));
+ int i;
+ for (i = 0; i < argc; ++i) {
+ strings[i] = NULL;
+ }
+ char* result = NULL;
+ int length = 0;
+ for (i = 0; i < argc; ++i) {
+ strings[i] = Evaluate(cookie, argv[i]);
+ if (strings[i] == NULL) {
+ goto done;
+ }
+ length += strlen(strings[i]);
+ }
+
+ result = malloc(length+1);
+ int p = 0;
+ for (i = 0; i < argc; ++i) {
+ strcpy(result+p, strings[i]);
+ p += strlen(strings[i]);
+ }
+ result[p] = '\0';
+
+done:
+ for (i = 0; i < argc; ++i) {
+ free(strings[i]);
+ }
+ return result;
+}
+
+char* IfElseFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ if (argc != 2 && argc != 3) {
+ return NULL;
+ }
+ char* cond = Evaluate(cookie, argv[0]);
+ if (cond == NULL) {
+ return NULL;
+ }
+
+ if (BooleanString(cond) == true) {
+ free(cond);
+ return Evaluate(cookie, argv[1]);
+ } else {
+ if (argc == 3) {
+ free(cond);
+ return Evaluate(cookie, argv[2]);
+ } else {
+ return cond;
+ }
+ }
+}
+
+char* AbortFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ return NULL;
+}
+
+char* AssertFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ int i;
+ for (i = 0; i < argc; ++i) {
+ char* v = Evaluate(cookie, argv[i]);
+ if (v == NULL) {
+ return NULL;
+ }
+ int b = BooleanString(v);
+ free(v);
+ if (!b) {
+ return NULL;
+ }
+ }
+ return strdup("");
+}
+
+char* PrintFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ int i;
+ for (i = 0; i < argc; ++i) {
+ char* v = Evaluate(cookie, argv[i]);
+ if (v == NULL) {
+ return NULL;
+ }
+ fputs(v, stdout);
+ free(v);
+ }
+ return strdup("");
+}
+
+char* LogicalAndFn(const char* name, void* cookie,
+ int argc, Expr* argv[]) {
+ char* left = Evaluate(cookie, argv[0]);
+ if (left == NULL) return NULL;
+ if (BooleanString(left) == true) {
+ free(left);
+ return Evaluate(cookie, argv[1]);
+ } else {
+ return left;
+ }
+}
+
+char* LogicalOrFn(const char* name, void* cookie,
+ int argc, Expr* argv[]) {
+ char* left = Evaluate(cookie, argv[0]);
+ if (left == NULL) return NULL;
+ if (BooleanString(left) == false) {
+ free(left);
+ return Evaluate(cookie, argv[1]);
+ } else {
+ return left;
+ }
+}
+
+char* LogicalNotFn(const char* name, void* cookie,
+ int argc, Expr* argv[]) {
+ char* val = Evaluate(cookie, argv[0]);
+ if (val == NULL) return NULL;
+ bool bv = BooleanString(val);
+ free(val);
+ if (bv) {
+ return strdup("");
+ } else {
+ return strdup("t");
+ }
+}
+
+char* SubstringFn(const char* name, void* cookie,
+ int argc, Expr* argv[]) {
+ char* needle = Evaluate(cookie, argv[0]);
+ if (needle == NULL) return NULL;
+ char* haystack = Evaluate(cookie, argv[1]);
+ if (haystack == NULL) {
+ free(needle);
+ return NULL;
+ }
+
+ char* result = strdup(strstr(haystack, needle) ? "t" : "");
+ free(needle);
+ free(haystack);
+ return result;
+}
+
+char* EqualityFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ char* left = Evaluate(cookie, argv[0]);
+ if (left == NULL) return NULL;
+ char* right = Evaluate(cookie, argv[1]);
+ if (right == NULL) {
+ free(left);
+ return NULL;
+ }
+
+ char* result = strdup(strcmp(left, right) == 0 ? "t" : "");
+ free(left);
+ free(right);
+ return result;
+}
+
+char* InequalityFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ char* left = Evaluate(cookie, argv[0]);
+ if (left == NULL) return NULL;
+ char* right = Evaluate(cookie, argv[1]);
+ if (right == NULL) {
+ free(left);
+ return NULL;
+ }
+
+ char* result = strdup(strcmp(left, right) != 0 ? "t" : "");
+ free(left);
+ free(right);
+ return result;
+}
+
+char* SequenceFn(const char* name, void* cookie, int argc, Expr* argv[]) {
+ char* left = Evaluate(cookie, argv[0]);
+ if (left == NULL) return NULL;
+ free(left);
+ return Evaluate(cookie, argv[1]);
+}
+
+char* Literal(const char* name, void* cookie, int argc, Expr* argv[]) {
+ return strdup(name);
+}
+
+Expr* Build(Function fn, int count, ...) {
+ va_list v;
+ va_start(v, count);
+ Expr* e = malloc(sizeof(Expr));
+ e->fn = fn;
+ e->name = "(operator)";
+ e->argc = count;
+ e->argv = malloc(count * sizeof(Expr*));
+ int i;
+ for (i = 0; i < count; ++i) {
+ e->argv[i] = va_arg(v, Expr*);
+ }
+ va_end(v);
+ return e;
+}
+
+static int fn_entries = 0;
+static int fn_size = 0;
+NamedFunction* fn_table = NULL;
+
+void RegisterFunction(const char* name, Function fn) {
+ if (fn_entries <= fn_size) {
+ fn_size = fn_size*2 + 1;
+ fn_table = realloc(fn_table, fn_size * sizeof(NamedFunction));
+ }
+ fn_table[fn_entries].name = name;
+ fn_table[fn_entries].fn = fn;
+ ++fn_entries;
+}
+
+static int fn_entry_compare(const void* a, const void* b) {
+ const char* na = ((const NamedFunction*)a)->name;
+ const char* nb = ((const NamedFunction*)b)->name;
+ return strcmp(na, nb);
+}
+
+void FinishRegistration() {
+ qsort(fn_table, fn_entries, sizeof(NamedFunction), fn_entry_compare);
+}
+
+Function FindFunction(const char* name) {
+ NamedFunction key;
+ key.name = name;
+ NamedFunction* nf = bsearch(&key, fn_table, fn_entries, sizeof(NamedFunction),
+ fn_entry_compare);
+ if (nf == NULL) {
+ return NULL;
+ }
+ return nf->fn;
+}
+
+void RegisterBuiltins() {
+ RegisterFunction("ifelse", IfElseFn);
+ RegisterFunction("abort", AbortFn);
+ RegisterFunction("assert", AssertFn);
+ RegisterFunction("concat", ConcatFn);
+ RegisterFunction("is_substring", SubstringFn);
+ RegisterFunction("print", PrintFn);
+}
diff --git a/edify/expr.h b/edify/expr.h
new file mode 100644
index 0000000..ac5df18
--- /dev/null
+++ b/edify/expr.h
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _EXPRESSION_H
+#define _EXPRESSION_H
+
+#define MAX_STRING_LEN 1024
+
+typedef struct Expr Expr;
+
+typedef char* (*Function)(const char* name, void* cookie,
+ int argc, Expr* argv[]);
+
+struct Expr {
+ Function fn;
+ char* name;
+ int argc;
+ Expr** argv;
+};
+
+char* Evaluate(void* cookie, Expr* expr);
+
+// Glue to make an Expr out of a literal.
+char* Literal(const char* name, void* cookie, int argc, Expr* argv[]);
+
+// Functions corresponding to various syntactic sugar operators.
+// ("concat" is also available as a builtin function, to concatenate
+// more than two strings.)
+char* ConcatFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* LogicalAndFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* LogicalOrFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* LogicalNotFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* SubstringFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* EqualityFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* InequalityFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* SequenceFn(const char* name, void* cookie, int argc, Expr* argv[]);
+
+// Convenience function for building expressions with a fixed number
+// of arguments.
+Expr* Build(Function fn, int count, ...);
+
+// Global builtins, registered by RegisterBuiltins().
+char* IfElseFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* AssertFn(const char* name, void* cookie, int argc, Expr* argv[]);
+char* AbortFn(const char* name, void* cookie, int argc, Expr* argv[]);
+
+typedef struct {
+ const char* name;
+ Function fn;
+} NamedFunction;
+
+// Register a new function. The same Function may be registered under
+// multiple names, but a given name should only be used once.
+void RegisterFunction(const char* name, Function fn);
+
+// Register all the builtins.
+void RegisterBuiltins();
+
+// Call this after all calls to RegisterFunction() but before parsing
+// any scripts to finish building the function table.
+void FinishRegistration();
+
+// Find the Function for a given name; return NULL if no such function
+// exists.
+Function FindFunction(const char* name);
+
+#endif // _EXPRESSION_H
diff --git a/edify/lexer.l b/edify/lexer.l
new file mode 100644
index 0000000..4faef5d
--- /dev/null
+++ b/edify/lexer.l
@@ -0,0 +1,97 @@
+%{
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "expr.h"
+#include "parser.h"
+
+int gLine = 1;
+int gColumn = 1;
+
+// TODO: enforce MAX_STRING_LEN during lexing
+char string_buffer[MAX_STRING_LEN];
+char* string_pos;
+%}
+
+%x STR
+
+%option noyywrap
+
+%%
+
+
+\" {
+ ++gColumn;
+ BEGIN(STR);
+ string_pos = string_buffer;
+}
+
+<STR>{
+ \" {
+ ++gColumn;
+ BEGIN(INITIAL);
+ *string_pos = '\0';
+ yylval.str = strdup(string_buffer);
+ return STRING;
+ }
+
+ \\n { gColumn += yyleng; *string_pos++ = '\n'; }
+ \\t { gColumn += yyleng; *string_pos++ = '\t'; }
+ \\\" { gColumn += yyleng; *string_pos++ = '\"'; }
+ \\\\ { gColumn += yyleng; *string_pos++ = '\\'; }
+
+ \\x[0-9a-fA-F]{2} {
+ gColumn += yyleng;
+ int val;
+ sscanf(yytext+2, "%x", &val);
+ *string_pos++ = val;
+ }
+
+ \n {
+ ++gLine;
+ gColumn = 1;
+ *string_pos++ = yytext[0];
+ }
+
+ . {
+ ++gColumn;
+ *string_pos++ = yytext[0];
+ }
+}
+
+if { gColumn += yyleng; return IF; }
+then { gColumn += yyleng; return THEN; }
+else { gColumn += yyleng; return ELSE; }
+endif { gColumn += yyleng; return ENDIF; }
+
+[a-zA-Z0-9_:/]+ {
+ gColumn += yyleng;
+ yylval.str = strdup(yytext);
+ return STRING;
+}
+
+\&\& { gColumn += yyleng; return AND; }
+\|\| { gColumn += yyleng; return OR; }
+== { gColumn += yyleng; return EQ; }
+!= { gColumn += yyleng; return NE; }
+
+[+(),!;] { gColumn += yyleng; return yytext[0]; }
+
+[ \t]+ gColumn += yyleng;
+
+(#.*)?\n { ++gLine; gColumn = 1; }
+
+. return BAD;
diff --git a/edify/main.c b/edify/main.c
new file mode 100644
index 0000000..4d65da2
--- /dev/null
+++ b/edify/main.c
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "expr.h"
+#include "parser.h"
+
+int expect(const char* expr_str, const char* expected, int* errors) {
+ Expr* e;
+ int error;
+ char* result;
+
+ printf(".");
+
+ yy_scan_string(expr_str);
+ error = yyparse(&e);
+ if (error > 0) {
+ fprintf(stderr, "error parsing \"%s\"\n", expr_str);
+ ++*errors;
+ return 0;
+ }
+
+ result = Evaluate(NULL, e);
+ if (result == NULL && expected != NULL) {
+ fprintf(stderr, "error evaluating \"%s\"\n", expr_str);
+ ++*errors;
+ return 0;
+ }
+
+ if (result == NULL && expected == NULL) {
+ return 1;
+ }
+
+ if (strcmp(result, expected) != 0) {
+ fprintf(stderr, "evaluating \"%s\": expected \"%s\", got \"%s\"\n",
+ expr_str, expected, result);
+ ++*errors;
+ free(result);
+ return 0;
+ }
+
+ free(result);
+ return 1;
+}
+
+int test() {
+ int errors = 0;
+
+ expect("a", "a", &errors);
+ expect("\"a\"", "a", &errors);
+ expect("\"\\x61\"", "a", &errors);
+ expect("# this is a comment\n"
+ " a\n"
+ " \n",
+ "a", &errors);
+
+
+ // sequence operator
+ expect("a; b; c", "c", &errors);
+
+ // string concat operator
+ expect("a + b", "ab", &errors);
+ expect("a + \n \"b\"", "ab", &errors);
+ expect("a + b +\nc\n", "abc", &errors);
+
+ // string concat function
+ expect("concat(a, b)", "ab", &errors);
+ expect("concat(a,\n \"b\")", "ab", &errors);
+ expect("concat(a + b,\nc,\"d\")", "abcd", &errors);
+ expect("\"concat\"(a + b,\nc,\"d\")", "abcd", &errors);
+
+ // logical and
+ expect("a && b", "b", &errors);
+ expect("a && \"\"", "", &errors);
+ expect("\"\" && b", "", &errors);
+ expect("\"\" && \"\"", "", &errors);
+ expect("\"\" && abort()", "", &errors); // test short-circuiting
+ expect("t && abort()", NULL, &errors);
+
+ // logical or
+ expect("a || b", "a", &errors);
+ expect("a || \"\"", "a", &errors);
+ expect("\"\" || b", "b", &errors);
+ expect("\"\" || \"\"", "", &errors);
+ expect("a || abort()", "a", &errors); // test short-circuiting
+ expect("\"\" || abort()", NULL, &errors);
+
+ // logical not
+ expect("!a", "", &errors);
+ expect("! \"\"", "t", &errors);
+ expect("!!a", "t", &errors);
+
+ // precedence
+ expect("\"\" == \"\" && b", "b", &errors);
+ expect("a + b == ab", "t", &errors);
+ expect("ab == a + b", "t", &errors);
+ expect("a + (b == ab)", "a", &errors);
+ expect("(ab == a) + b", "b", &errors);
+
+ // substring function
+ expect("is_substring(cad, abracadabra)", "t", &errors);
+ expect("is_substring(abrac, abracadabra)", "t", &errors);
+ expect("is_substring(dabra, abracadabra)", "t", &errors);
+ expect("is_substring(cad, abracxadabra)", "", &errors);
+ expect("is_substring(abrac, axbracadabra)", "", &errors);
+ expect("is_substring(dabra, abracadabrxa)", "", &errors);
+
+ // ifelse function
+ expect("ifelse(t, yes, no)", "yes", &errors);
+ expect("ifelse(!t, yes, no)", "no", &errors);
+ expect("ifelse(t, yes, abort())", "yes", &errors);
+ expect("ifelse(!t, abort(), no)", "no", &errors);
+
+ // if "statements"
+ expect("if t then yes else no endif", "yes", &errors);
+ expect("if \"\" then yes else no endif", "no", &errors);
+ expect("if \"\" then yes endif", "", &errors);
+ expect("if \"\"; t then yes endif", "yes", &errors);
+
+ printf("\n");
+
+ return errors;
+}
+
+int main(int argc, char** argv) {
+ RegisterBuiltins();
+ FinishRegistration();
+
+ if (argc == 1) {
+ return test() != 0;
+ }
+
+ FILE* f = fopen(argv[1], "r");
+ char buffer[8192];
+ int size = fread(buffer, 1, 8191, f);
+ fclose(f);
+ buffer[size] = '\0';
+
+ Expr* root;
+ yy_scan_bytes(buffer, size);
+ int error = yyparse(&root);
+ printf("parse returned %d\n", error);
+ if (error == 0) {
+ char* result = Evaluate(NULL, root);
+ printf("result is [%s]\n", result == NULL ? "(NULL)" : result);
+ }
+ return 0;
+}
diff --git a/edify/parser.y b/edify/parser.y
new file mode 100644
index 0000000..67a210f
--- /dev/null
+++ b/edify/parser.y
@@ -0,0 +1,121 @@
+%{
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "expr.h"
+#include "parser.h"
+
+extern int gLine;
+extern int gColumn;
+
+void yyerror(Expr** root, const char* s);
+int yyparse(Expr** root);
+
+%}
+
+%union {
+ char* str;
+ Expr* expr;
+ struct {
+ int argc;
+ Expr** argv;
+ } args;
+}
+
+%token AND OR SUBSTR SUPERSTR EQ NE IF THEN ELSE ENDIF
+%token <str> STRING BAD
+%type <expr> expr
+%type <args> arglist
+
+%parse-param {Expr** root}
+%error-verbose
+
+/* declarations in increasing order of precedence */
+%left ';'
+%left ','
+%left OR
+%left AND
+%left EQ NE
+%left '+'
+%right '!'
+
+%%
+
+input: expr { *root = $1; }
+;
+
+expr: STRING {
+ $$ = malloc(sizeof(Expr));
+ $$->fn = Literal;
+ $$->name = $1;
+ $$->argc = 0;
+ $$->argv = NULL;
+}
+| '(' expr ')' { $$ = $2; }
+| expr ';' { $$ = $1; }
+| expr ';' expr { $$ = Build(SequenceFn, 2, $1, $3); }
+| error ';' expr { $$ = $3; }
+| expr '+' expr { $$ = Build(ConcatFn, 2, $1, $3); }
+| expr EQ expr { $$ = Build(EqualityFn, 2, $1, $3); }
+| expr NE expr { $$ = Build(InequalityFn, 2, $1, $3); }
+| expr AND expr { $$ = Build(LogicalAndFn, 2, $1, $3); }
+| expr OR expr { $$ = Build(LogicalOrFn, 2, $1, $3); }
+| '!' expr { $$ = Build(LogicalNotFn, 1, $2); }
+| IF expr THEN expr ENDIF { $$ = Build(IfElseFn, 2, $2, $4); }
+| IF expr THEN expr ELSE expr ENDIF { $$ = Build(IfElseFn, 3, $2, $4, $6); }
+| STRING '(' arglist ')' {
+ $$ = malloc(sizeof(Expr));
+ $$->fn = FindFunction($1);
+ if ($$->fn == NULL) {
+ char buffer[256];
+ snprintf(buffer, sizeof(buffer), "unknown function \"%s\"", $1);
+ yyerror(root, buffer);
+ YYERROR;
+ }
+ $$->name = $1;
+ $$->argc = $3.argc;
+ $$->argv = $3.argv;
+}
+;
+
+arglist: /* empty */ {
+ $$.argc = 0;
+ $$.argv = NULL;
+}
+| expr {
+ $$.argc = 1;
+ $$.argv = malloc(sizeof(Expr*));
+ $$.argv[0] = $1;
+}
+| arglist ',' expr {
+ $$.argc = $1.argc + 1;
+ $$.argv = realloc($$.argv, $$.argc * sizeof(Expr*));
+ $$.argv[$$.argc-1] = $3;
+}
+;
+
+%%
+
+void yyerror(Expr** root, const char* s) {
+ if (strlen(s) == 0) {
+ s = "syntax error";
+ }
+ printf("line %d col %d: %s\n", gLine, gColumn, s);
+}