You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@corinthia.apache.org by pm...@apache.org on 2015/08/05 14:42:31 UTC
incubator-corinthia git commit: Flat: Add support for String
expressions
Repository: incubator-corinthia
Updated Branches:
refs/heads/master 2545a4e6e -> e9ffeb107
Flat: Add support for String expressions
Parsing expression grammars (PEGs) make no distinction between lexical
and syntactic analysis. The same constructs are used for expressing the
what "tokens" (e.g. identifier or symbol) and "productions" (e.g.
expression) look like.
Because of the simplistic parse tree construction method we've used to
date, the tree resulting from a parse contains a very large number of
nodes, many of which represent components of what would normally be
considered "tokens". These include leaf nodes for every single character
found, and interior nnodes for things like choice and repetition
constructs.
All these extra nodes are generally not of interest - it is usually more
convenient to have, for example, an Identifier as a single node in the
tree, represented by its string value.
With this commit, the grammar format now supports expressions of the
form $(...), where the inner expression will result in a single node
being generated in the parse tree. This does not affect the set of
strings accepted for a given language, but is merely an instruction to
the parser on how to represent what it finds.
Project: http://git-wip-us.apache.org/repos/asf/incubator-corinthia/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-corinthia/commit/e9ffeb10
Tree: http://git-wip-us.apache.org/repos/asf/incubator-corinthia/tree/e9ffeb10
Diff: http://git-wip-us.apache.org/repos/asf/incubator-corinthia/diff/e9ffeb10
Branch: refs/heads/master
Commit: e9ffeb1074e374934093ac3a4eaf49f250291934
Parents: 2545a4e
Author: Peter Kelly <pe...@uxproductivity.com>
Authored: Wed Aug 5 19:10:04 2015 +0700
Committer: Peter Kelly <pe...@uxproductivity.com>
Committed: Wed Aug 5 19:38:02 2015 +0700
----------------------------------------------------------------------
experiments/flat/grammars/peg.peg | 6 ++++--
experiments/flat/src/BuildGrammar.c | 37 +++++++++++++-------------------
experiments/flat/src/Builtin.c | 11 +++++++---
experiments/flat/src/Builtin.h | 10 +++++----
experiments/flat/src/Expression.c | 35 +++++++++++++++++++++++++++---
experiments/flat/src/Expression.h | 10 +++++++++
experiments/flat/src/Parser.c | 8 +++++++
experiments/flat/src/Term.c | 3 ++-
experiments/flat/src/flat.c | 8 ++++---
9 files changed, 90 insertions(+), 38 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/grammars/peg.peg
----------------------------------------------------------------------
diff --git a/experiments/flat/grammars/peg.peg b/experiments/flat/grammars/peg.peg
index 9de9394..8c70d19 100644
--- a/experiments/flat/grammars/peg.peg
+++ b/experiments/flat/grammars/peg.peg
@@ -5,11 +5,12 @@ Sequence <- Prefix*
Prefix <- (AND / NOT)? Suffix
Suffix <- Primary (QUESTION / STAR / PLUS)?
Primary <- Identifier !LEFTARROW
+ / DOLLAR OPEN Expression CLOSE
/ OPEN Expression CLOSE
/ Literal
/ Class
/ DOT
-Identifier <- IdentStart IdentCont* Spacing
+Identifier <- $(IdentStart IdentCont*) Spacing
IdentStart <- [a-zA-Z_]
IdentCont <- IdentStart
/ [0-9]
@@ -32,7 +33,8 @@ PLUS <- '+' Spacing
OPEN <- '(' Spacing
CLOSE <- ')' Spacing
DOT <- '.' Spacing
-Spacing <- (Space / Comment)*
+DOLLAR <- '$' Spacing
+Spacing <- $((Space / Comment)*)
Comment <- '#' (!EndOfLine .)* EndOfLine
Space <- ' '
/ '\t'
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/BuildGrammar.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/BuildGrammar.c b/experiments/flat/src/BuildGrammar.c
index fd3a169..ea066a5 100644
--- a/experiments/flat/src/BuildGrammar.c
+++ b/experiments/flat/src/BuildGrammar.c
@@ -114,29 +114,16 @@ static char *termString(Builder *builder, Term *term)
return str;
}
-static char *termChildrenString(Builder *builder, Term *term, int firstIndex, int lastIndex)
-{
- Term *firstChild = TermChildAt(term,firstIndex);
- Term *lastChild = TermChildAt(term,lastIndex);
- int start = firstChild->start;
- int end = lastChild->end;
-
- assert(start >= 0);
- assert(end <= builder->len);
- int len = end - start;
- char *str = malloc(len+1);
- memcpy(str,&builder->input[start],len);
- str[len] = '\0';
-
- return str;
-}
-
static char *identifierString(Builder *builder, Term *term)
{
assert(isIdent(term,"Identifier"));
Term *body = TermChildAt(term,0);
- assert(isSequence(body,3));
- return termChildrenString(builder,body,0,1);
+ assert(isSequence(body,2));
+ Term *content = TermChildAt(body,0);
+ Term *spacing = TermChildAt(body,1);
+ assert(TermKind(content) == StringExpr);
+ assert(isIdent(spacing,"Spacing"));
+ return termString(builder,content);
}
// For Terms of type ChoiceExpr, determine which of the choices the corresponding term is
@@ -310,15 +297,21 @@ static Expression *buildPrimary(Builder *builder, Term *term)
return buildIdentifier(builder,identifier);
}
case 1: {
+ assert(isSequence(choice,4));
+ Term *expression = TermChildAt(choice,2);
+ Expression *result = buildExpression(builder,expression);
+ return ExpressionNewString(result);
+ }
+ case 2: {
assert(isSequence(choice,3));
Term *expression = TermChildAt(choice,1);
return buildExpression(builder,expression);
}
- case 2:
- return buildLiteral(builder,choice);
case 3:
- return buildClass(builder,choice);
+ return buildLiteral(builder,choice);
case 4:
+ return buildClass(builder,choice);
+ case 5:
return buildDot(builder,choice);
default:
assert(!"Invalid choice for Primary");
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Builtin.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Builtin.c b/experiments/flat/src/Builtin.c
index ee8fb81..3db323b 100644
--- a/experiments/flat/src/Builtin.c
+++ b/experiments/flat/src/Builtin.c
@@ -31,6 +31,7 @@
#define lit(value) ExpressionNewLit(value)
#define cls(...) makeExpression(ExpressionNewClass,__VA_ARGS__,NULL)
#define dot() ExpressionNewDot()
+#define string(child) ExpressionNewString(child)
#define range(lo,hi) ExpressionNewRange(lo,hi)
static Expression *makeExpression(Expression *(*fun)(int,Expression **), ...)
@@ -90,6 +91,7 @@ Grammar *GrammarNewBuiltin(void)
// / DOT
GrammarDefine(gram,"Primary",
choice(seq(ref("Identifier"),not(ref("LEFTARROW"))),
+ seq(ref("DOLLAR"),ref("OPEN"),ref("Expression"),ref("CLOSE")),
seq(ref("OPEN"),ref("Expression"),ref("CLOSE")),
ref("Literal"),
ref("Class"),
@@ -97,8 +99,8 @@ Grammar *GrammarNewBuiltin(void)
// Identifier <- IdentStart IdentCont* Spacing
GrammarDefine(gram,"Identifier",
- seq(ref("IdentStart"),
- star(ref("IdentCont")),
+ seq(string(seq(ref("IdentStart"),
+ star(ref("IdentCont")))),
ref("Spacing")));
// IdentStart <- [a-zA-Z_]
@@ -195,8 +197,11 @@ Grammar *GrammarNewBuiltin(void)
// DOT <- '.' Spacing
GrammarDefine(gram,"DOT",seq(lit("."),ref("Spacing")));
+ // DOLLAR <- '$' Spacing
+ GrammarDefine(gram,"DOLLAR",seq(lit("$"),ref("Spacing")));
+
// Spacing <- (Space / Comment)*
- GrammarDefine(gram,"Spacing",star(choice(ref("Space"),ref("Comment"))));
+ GrammarDefine(gram,"Spacing",string(star(choice(ref("Space"),ref("Comment")))));
// Comment <- '#' (!EndOfLine .)* EndOfLine
GrammarDefine(gram,"Comment",
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Builtin.h
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Builtin.h b/experiments/flat/src/Builtin.h
index 34ea272..089f068 100644
--- a/experiments/flat/src/Builtin.h
+++ b/experiments/flat/src/Builtin.h
@@ -20,8 +20,8 @@
#include "Grammar.h"
/**
- * The GrammarNewBuiltin() function creates the following Grammar, which comes
- * from Ford's original PEG paper:
+ * The GrammarNewBuiltin() function creates the grammar shown below, which is based on the one from
+ * Ford's original PEG paper.
*
* Grammar <- Spacing Definition+ EndOfFile
* Definition <- Identifier LEFTARROW Expression
@@ -30,11 +30,12 @@
* Prefix <- (AND / NOT)? Suffix
* Suffix <- Primary (QUESTION / STAR / PLUS)?
* Primary <- Identifier !LEFTARROW
+ * / DOLLAR OPEN Expression CLOSE
* / OPEN Expression CLOSE
* / Literal
* / Class
* / DOT
- * Identifier <- IdentStart IdentCont* Spacing
+ * Identifier <- $(IdentStart IdentCont*) Spacing
* IdentStart <- [a-zA-Z_]
* IdentCont <- IdentStart
* / [0-9]
@@ -57,7 +58,8 @@
* OPEN <- '(' Spacing
* CLOSE <- ')' Spacing
* DOT <- '.' Spacing
- * Spacing <- (Space / Comment)*
+ * DOLLAR <- '$' Spacing
+ * Spacing <- $((Space / Comment)*)
* Comment <- '#' (!EndOfLine .)* EndOfLine
* Space <- ' '
* / '\t'
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Expression.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Expression.c b/experiments/flat/src/Expression.c
index 3a9873d..98b815c 100644
--- a/experiments/flat/src/Expression.c
+++ b/experiments/flat/src/Expression.c
@@ -59,9 +59,10 @@ const char *ExprKindAsString(ExprKind kind)
return "Dot";
case RangeExpr:
return "Range";
- default:
- return "?";
+ case StringExpr:
+ return "String";
}
+ return "?";
}
Expression *ExpressionNewChoice(int count, Expression **children)
@@ -186,6 +187,16 @@ Expression *ExpressionNewRange(int lo, int hi)
return expr;
}
+Expression *ExpressionNewString(Expression *child)
+{
+ assert(child != NULL);
+ Expression *expr = (Expression *)calloc(1,sizeof(Expression)+1*sizeof(Expression *));
+ expr->kind = StringExpr;
+ expr->count = 1;
+ expr->children[0] = child;
+ return expr;
+}
+
void ExpressionFree(Expression *expr)
{
if (expr == NULL)
@@ -220,8 +231,10 @@ static int ExprKindPrecedence(ExprKind kind)
case ClassExpr:
case DotExpr:
return 5;
- case RangeExpr:
+ case StringExpr:
return 6;
+ case RangeExpr:
+ return 7;
}
return 0;
}
@@ -310,6 +323,12 @@ void ExpressionPrint(Expression *expr, int highestPrecedence, const char *indent
}
break;
}
+ case StringExpr:
+ printf("$(");
+ highestPrecedence = 1; // because of brackets
+ ExpressionPrint(ExprStringChild(expr),highestPrecedence,NULL);
+ printf(")");
+ break;
}
if (brackets)
printf(")");
@@ -465,3 +484,13 @@ int ExprRangeEnd(Expression *expr)
assert(expr->kind == RangeExpr);
return expr->end;
}
+
+// String
+
+Expression *ExprStringChild(Expression *expr)
+{
+ assert(expr->kind == StringExpr);
+ assert(expr->count == 1);
+ assert(expr->children[0] != NULL);
+ return expr->children[0];
+}
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Expression.h
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Expression.h b/experiments/flat/src/Expression.h
index 3acb875..1058be0 100644
--- a/experiments/flat/src/Expression.h
+++ b/experiments/flat/src/Expression.h
@@ -69,6 +69,10 @@
*
* RangeExpr - Matches again a character that is between a specified minimum and maximum. Evaluation
* succeeds if the next input character c is such that start <= c < end.
+ *
+ * StringExpr - Instructs the parser to construct a single node in the parse tree representing
+ * everything within the child expression. Doesn't have any effect on what is or isn't accepted
+ * by the parser.
*/
typedef enum {
@@ -84,6 +88,7 @@ typedef enum {
ClassExpr,
DotExpr,
RangeExpr,
+ StringExpr,
} ExprKind;
typedef struct Expression Expression;
@@ -102,6 +107,7 @@ Expression *ExpressionNewLit(const char *value);
Expression *ExpressionNewClass(int count, Expression **children);
Expression *ExpressionNewDot(void);
Expression *ExpressionNewRange(int lo, int hi);
+Expression *ExpressionNewString(Expression *child);
void ExpressionFree(Expression *expr);
void ExpressionPrint(Expression *expr, int highestPrecedence, const char *indent);
@@ -143,3 +149,7 @@ Expression *ExprClassChildAt(Expression *expr, int index);
int ExprRangeStart(Expression *expr);
int ExprRangeEnd(Expression *expr);
+
+// String
+
+Expression *ExprStringChild(Expression *expr);
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Parser.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Parser.c b/experiments/flat/src/Parser.c
index 0425b33..74c1e28 100644
--- a/experiments/flat/src/Parser.c
+++ b/experiments/flat/src/Parser.c
@@ -204,6 +204,14 @@ static Term *parseExpr(Parser *p, Expression *expr)
return NULL;
}
}
+ case StringExpr: {
+ Term *term = parseExpr(p,ExprStringChild(expr));
+ if (term == NULL)
+ return NULL;
+ // We ignore the parsed term here, since we're only interested in the string content
+ // (which can be recovered from the input, and the start and end fields of the term).
+ return TermNew(expr,startPos,p->pos,NULL);
+ }
}
assert(!"unknown expression type");
return NULL;
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/Term.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/Term.c b/experiments/flat/src/Term.c
index f8b331f..e3fc44b 100644
--- a/experiments/flat/src/Term.c
+++ b/experiments/flat/src/Term.c
@@ -107,7 +107,8 @@ void TermPrint(Term *term, const char *input, const char *indent)
break;
case LitExpr:
case RangeExpr:
- case DotExpr: {
+ case DotExpr:
+ case StringExpr: {
int start = term->start;
int end = term->end;
int inputLen = strlen(input);
http://git-wip-us.apache.org/repos/asf/incubator-corinthia/blob/e9ffeb10/experiments/flat/src/flat.c
----------------------------------------------------------------------
diff --git a/experiments/flat/src/flat.c b/experiments/flat/src/flat.c
index 7ed03d3..8aa4f74 100644
--- a/experiments/flat/src/flat.c
+++ b/experiments/flat/src/flat.c
@@ -28,10 +28,8 @@
static char *readStringFromFile(const char *filename)
{
FILE *f = fopen(filename,"rb");
- if (f == NULL) {
- perror(filename);
+ if (f == NULL)
return NULL;
- }
char *data = (char *)malloc(READ_SIZE);
size_t len = 0;
@@ -64,6 +62,10 @@ int main(int argc, const char **argv)
}
Grammar *gram = GrammarNewBuiltin();
Term *term = parse(gram,"Grammar",input,0,strlen(input));
+ if (term == NULL) {
+ fprintf(stderr,"%s: Parse failed\n",filename);
+ exit(1);
+ }
TermPrint(term,input,"");
free(input);
GrammarFree(gram);