| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you 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 "Common.h" |
| #include "BuildGrammar.h" |
| #include "Util.h" |
| #include <stdlib.h> |
| #include <stdio.h> |
| #include <string.h> |
| #include <assert.h> |
| |
| #define MAX_CHILDREN 64 |
| |
| typedef struct Builder Builder; |
| |
| struct Builder { |
| Grammar *gram; |
| const char *input; |
| int len; |
| }; |
| |
| static Expression *buildExpression(Builder *builder, Term *term); |
| |
| static char *unescapeLiteral(const char *escaped) |
| { |
| size_t escapedLen = strlen(escaped); |
| size_t escapedPos = 0; |
| size_t unescapedLen = 0; |
| char *unescaped = (char *)malloc(escapedLen+1); |
| |
| while (escapedPos < escapedLen) { |
| char c = escaped[escapedPos++]; |
| if ((c == '\\') && (escapedPos < escapedLen)) { |
| c = escaped[escapedPos++]; |
| switch (c) { |
| case 'n': |
| unescaped[unescapedLen++] = '\n'; |
| break; |
| case 'r': |
| unescaped[unescapedLen++] = '\r'; |
| break; |
| case 't': |
| unescaped[unescapedLen++] = '\t'; |
| break; |
| default: |
| unescaped[unescapedLen++] = c; |
| break; |
| } |
| } |
| else { |
| unescaped[unescapedLen++] = c; |
| } |
| } |
| |
| unescaped[unescapedLen] = '\0'; |
| return unescaped; |
| } |
| |
| // Sanity checking functions |
| // |
| // These are just used to verify that a Term we're about to use is of the expected type. |
| // Since the format of the parse tree is likely to change in these early stages of development, |
| // this will catch cases where the code in this file has not been adapted to those changes |
| // |
| // The large number of assert statements in this file, most of which use these functions, will |
| // likely only be necessary in the short term. Ideally we should be able to get to a point where |
| // one can safely write code that consumes a parse tree without having so many sanity checks. |
| |
| static int isTerm(Term *term, ExprKind kind, int count) |
| { |
| return ((TermKind(term) == kind) && (TermCount(term) == count)); |
| } |
| |
| static int isSequence(Term *term, int count) |
| { |
| return isTerm(term,SequenceExpr,count); |
| } |
| |
| static int isIdent(Term *term, const char *name) |
| { |
| return (isTerm(term,IdentExpr,1) && !strcmp(name,ExprIdentValue(TermType(term)))); |
| } |
| |
| // Extract a substring of the input based on a specific term, or one or more children of a term. |
| // |
| // Each Term object has a start and end field, which specify which portion of the input string |
| // the term covers (that is, the portion of the input consumed durin parsing of that term). In |
| // some cases we want all the text matched by a term, and in others we only want the text matched |
| // by specific children. An example of the latter is a "pseudo-terminal" like Identifier where |
| // we want all characters except the trailing whitespace. |
| |
| static char *termString(Builder *builder, Term *term) |
| { |
| assert(term->start >= 0); |
| assert(term->end <= builder->len); |
| int len = term->end - term->start; |
| char *str = malloc(len+1); |
| memcpy(str,&builder->input[term->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,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 |
| |
| static int choiceIndex(Term *body) |
| { |
| assert(TermKind(body) == ChoiceExpr); |
| assert(TermCount(body) == 1); |
| Term *choice = TermChildAt(body,0); |
| int match = -1; |
| int choiceCount = ExprChoiceCount(TermType(body)); |
| for (int i = 0; i < choiceCount; i++) { |
| if (TermType(choice) == ExpressionChildAt(TermType(body),i)) |
| match = i; |
| } |
| return match; |
| } |
| |
| // Expression building functions (build*) |
| // |
| // There is one of these for each type of expression that can be present in the grammar. The |
| // supplied Term object is, in all cases, of an IdentExpr type, whose single child is the body |
| // of the corresponding grammar rule. |
| // |
| // For example, buildPrimary is called with an ExpressionType of IdentExpr "Primary", and the |
| // body is a ChoiceExpr which can contain one of five possible child types, as given in the |
| // PEG grammar. |
| // |
| // To see the exact expression tree of a given rule, look at its definition in Builtin.c |
| |
| static Expression *buildIdentifier(Builder *builder, Term *term) |
| { |
| char *str = identifierString(builder,term); |
| Expression *result = ExpressionNewIdent(str); |
| free(str); |
| return result; |
| } |
| |
| static Expression *buildLiteral(Builder *builder, Term *term) |
| { |
| // The Literal rule in the built-in PEG grammar contains two choices - one for single quotes |
| // and the other for double quotes - which otherwise have the same structure. There are four |
| // children, where child 0 and child 2 represent the quotes themselves, child 1 represents the |
| // escaped representation of a string, and child 3 is any trailing whitespace. |
| // |
| // All we're interested in is the unescaped string, so we get child 2 and convert any escape |
| // sequences (e.g. \" or \n) to the characters they represent, and return a new literal |
| // expression with the unescaped string as its value. |
| |
| assert(isIdent(term,"Literal")); |
| Term *body = TermChildAt(term,0); |
| assert(TermKind(body) == ChoiceExpr); |
| int index = choiceIndex(body); |
| assert((index == 0) || (index == 1)); |
| Term *choice = TermChildAt(body,0); |
| assert(isSequence(choice,4)); |
| Term *content = TermChildAt(choice,1); |
| char *escaped = termString(builder,content); |
| char *unescaped = unescapeLiteral(escaped); |
| Expression *result = ExpressionNewLit(unescaped); |
| free(escaped); |
| free(unescaped); |
| return result; |
| } |
| |
| static int decodeRangeChar(Builder *builder, Term *charTerm) |
| { |
| // FIXME: Handle non-ASCII chars encoded as UTF-8, as well as numeric escape sequences |
| // We don't need to allocate a string for unescaped here, we should just do it directly |
| |
| assert(isIdent(charTerm,"Char")); |
| char *escaped = termString(builder,charTerm); |
| char *unescaped = unescapeLiteral(escaped); |
| int result; |
| if (strlen(unescaped) == 0) |
| result = '?'; |
| else if (unescaped[0] < 0) // Start of UTF-8 multibyte sequence |
| result = '?'; |
| else |
| result = unescaped[0]; |
| free(escaped); |
| free(unescaped); |
| return result; |
| } |
| |
| static Expression *buildRange(Builder *builder, Term *term) |
| { |
| // A range expression, one or more of which appear inside a [...] character class expression, |
| // matches a character in a range between a start and end value. We use a single expression |
| // type to represent both exact matches (where the minimum and maximum are the same), and |
| // "true" ranges (which match two or more possible characters). |
| // |
| // Note that the representation we use for Range expressions is a (start,end) pair, where a |
| // character match must satisfy the condition start <= c < end (that is, the range includes the |
| // start, but does *not* include the end). This representation is for the convenience of other |
| // code that works with ranges. The ExpressionNewRange function however takes the minimum and |
| // maximum values - that is, a matching character c must satisfy min <= c <= max. |
| |
| assert(isIdent(term,"Range")); |
| Term *body = TermChildAt(term,0); |
| int index = choiceIndex(body); |
| Term *choice = TermChildAt(body,0); |
| assert((index == 0) || (index == 1)); |
| if (index == 0) { |
| assert(isSequence(choice,3)); |
| Term *minChar = TermChildAt(choice,0); |
| Term *maxChar = TermChildAt(choice,2); |
| assert(isIdent(minChar,"Char")); |
| assert(isIdent(maxChar,"Char")); |
| int min = decodeRangeChar(builder,minChar); |
| int max = decodeRangeChar(builder,maxChar); |
| return ExpressionNewRange(min,max); |
| } |
| else { |
| assert(isIdent(choice,"Char")); |
| int value = decodeRangeChar(builder,choice); |
| return ExpressionNewRange(value,value); |
| } |
| } |
| |
| static Expression *buildClass(Builder *builder, Term *term) |
| { |
| // A character class expression is the same as a choice expression, except that it is only |
| // supposed to contain range expressions. |
| |
| assert(isIdent(term,"Class")); |
| Term *body = TermChildAt(term,0); |
| assert(isSequence(body,4)); |
| Term *star = TermChildAt(body,1); |
| assert(TermKind(star) == StarExpr); |
| |
| Expression *children[MAX_CHILDREN]; |
| int count = 0; |
| for (TermList *item = TermChildren(star); (item != NULL) && (count < MAX_CHILDREN); item = item->next) { |
| assert(isSequence(item->term,2)); |
| Term *rangeTerm = TermChildAt(item->term,1); |
| Expression *rangeExpr = buildRange(builder,rangeTerm); |
| children[count++] = rangeExpr; |
| } |
| |
| return ExpressionNewClass(count,children); |
| } |
| |
| static Expression *buildDot(Builder *builder, Term *term) |
| { |
| assert(isIdent(term,"DOT")); |
| return ExpressionNewDot(); |
| } |
| |
| static Expression *buildPrimary(Builder *builder, Term *term) |
| { |
| // A primary expression can be one of five possibilities: An identifier (reference to another |
| // rule in the grammar), a parenthesised expresion, a literal, a character class, or a dot |
| // (which matches any character). |
| // |
| // The type of the term is an Expression with kind == ChoiceExpr, and the term has exactly |
| // one child. We use choiceIndex to determine which of the five possible expression types |
| // the choice matches, and then call through to the relevant function to build the appropriate |
| // type of Expression object. |
| |
| assert(isIdent(term,"Primary")); |
| Term *body = TermChildAt(term,0); |
| assert(TermKind(body) == ChoiceExpr); |
| assert(TermCount(body) == 1); |
| Term *choice = TermChildAt(body,0); |
| |
| switch (choiceIndex(body)) { |
| case 0: { |
| assert(isSequence(choice,2)); |
| Term *identifier = TermChildAt(choice,0); |
| 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 3: |
| return buildLiteral(builder,choice); |
| case 4: |
| return buildClass(builder,choice); |
| case 5: |
| return buildDot(builder,choice); |
| default: |
| assert(!"Invalid choice for Primary"); |
| return NULL; |
| } |
| } |
| |
| static Expression *buildSuffix(Builder *builder, Term *term) |
| { |
| // A suffix expression has two children. The second is optional, and is one of either QUESTION, |
| // STAR, or PLUS - which indicate that the first child may occur zero or one times, zero or more |
| // times, or one or more times. The first child is always present, and represents a primary |
| // expression with no prefix or suffix. |
| // |
| // If a QUESTION, STAR, or PLUS suffix is given, we wrap the constructed primary expression |
| // inside another Expression object of type OptExpr, StarExpr, or PlusExpr. Otherwise, we just |
| // return the primary expression directly. |
| |
| assert(isIdent(term,"Suffix")); |
| Term *body = TermChildAt(term,0); |
| assert(isSequence(body,2)); |
| Term *primary = TermChildAt(body,0); |
| Term *suffix = TermChildAt(body,1); |
| assert(isIdent(primary,"Primary")); |
| assert(TermKind(suffix) == OptExpr); |
| |
| Expression *primaryExpr = buildPrimary(builder,primary); |
| |
| assert((TermCount(suffix) == 0) || (TermCount(suffix) == 1)); |
| if (TermCount(suffix) == 1) { |
| Term *suffixChild = TermChildAt(suffix,0); |
| int index = choiceIndex(suffixChild); |
| Term *choice = TermChildAt(suffixChild,0); |
| switch (index) { |
| case 0: |
| assert(isIdent(choice,"QUESTION")); |
| return ExpressionNewOpt(primaryExpr); |
| case 1: |
| assert(isIdent(choice,"STAR")); |
| return ExpressionNewStar(primaryExpr); |
| case 2: |
| assert(isIdent(choice,"PLUS")); |
| return ExpressionNewPlus(primaryExpr); |
| default: |
| assert(!"Invalid choice for Suffix"); |
| break; |
| } |
| } |
| |
| return primaryExpr; |
| } |
| |
| static Expression *buildPrefix(Builder *builder, Term *term) |
| { |
| // A prefix expression has two children. The first is optional, and is one of either AND or |
| // NOT - which indicate a positive or negative lookahead assertion. The second is not optional, |
| // and represents a primary expression with an optional suffix. |
| // |
| // If an AND or NOT prefx is given, we wrap the constructed primary expression inside another |
| // Expression object of type AndExpr or NotExpr. Otherwise, we just return the primary |
| // expression directly. |
| |
| assert(isIdent(term,"Prefix")); |
| Term *body = TermChildAt(term,0); |
| assert(isSequence(body,2)); |
| Term *prefix = TermChildAt(body,0); |
| Term *suffix = TermChildAt(body,1); |
| assert(TermKind(prefix) == OptExpr); |
| assert(isIdent(suffix,"Suffix")); |
| |
| Expression *suffixExpr = buildSuffix(builder,suffix); |
| |
| assert((TermCount(prefix) == 0) || (TermCount(prefix) == 1)); |
| if (TermCount(prefix) == 1) { |
| Term *prefixChild = TermChildAt(prefix,0); |
| int index = choiceIndex(prefixChild); |
| Term *choice = TermChildAt(prefixChild,0); |
| switch (index) { |
| case 0: |
| assert(isIdent(choice,"AND")); |
| return ExpressionNewAnd(suffixExpr); |
| case 1: |
| assert(isIdent(choice,"NOT")); |
| return ExpressionNewNot(suffixExpr); |
| default: |
| assert(!"Invalid choice for Prefix"); |
| break; |
| } |
| } |
| |
| return suffixExpr; |
| } |
| |
| static Expression *buildSequence(Builder *builder, Term *term) |
| { |
| // An Sequence consists of one or more expressions, each of which has an optional prefix |
| // and suffix |
| assert(isIdent(term,"Sequence")); |
| Term *body = TermChildAt(term,0); |
| assert(TermKind(body) == StarExpr); |
| |
| Expression *children[MAX_CHILDREN]; |
| int count = 0; |
| for (TermList *item = TermChildren(body); (item != NULL) && (count < MAX_CHILDREN); item = item->next) { |
| children[count] = buildPrefix(builder,item->term); |
| count++; |
| } |
| if (count == 1) |
| return children[0]; |
| else |
| return ExpressionNewSequence(count,children); |
| } |
| |
| static Expression *buildExpression(Builder *builder, Term *term) |
| { |
| // An Expression consists of one or more choices |
| assert(isIdent(term,"Expression")); |
| Term *body = TermChildAt(term,0); |
| assert(isSequence(body,2)); |
| |
| Term *child0 = TermChildAt(body,0); |
| Term *child1 = TermChildAt(body,1); |
| |
| assert(isIdent(child0,"Sequence")); |
| assert(TermKind(child1) == StarExpr); |
| |
| Expression *initial = buildSequence(builder,child0); |
| if (TermCount(child1) == 0) |
| return initial; |
| |
| Expression *children[MAX_CHILDREN]; |
| children[0] = initial; |
| int count = 1; |
| for (TermList *item = TermChildren(child1); (item != NULL) && (count < MAX_CHILDREN); item = item->next) { |
| assert(isSequence(item->term,2)); |
| children[count] = buildSequence(builder,TermChildAt(item->term,1)); |
| count++; |
| } |
| return ExpressionNewChoice(count,children); |
| } |
| |
| static void buildGrammar(Builder *builder, Term *term) |
| { |
| assert(isSequence(term,3)); |
| Term *plus = TermChildAt(term,1); |
| assert(TermKind(plus) == PlusExpr); |
| |
| for (TermList *plusItem = plus->children; plusItem != NULL; plusItem = plusItem->next) { |
| Term *defIdent = plusItem->term; |
| assert(isIdent(defIdent,"Definition")); |
| Term *defSeq = TermChildAt(defIdent,0); |
| assert(isSequence(defSeq,4)); |
| Term *identTerm = TermChildAt(defSeq,0); |
| Term *exprTerm = TermChildAt(defSeq,2); |
| assert(isIdent(identTerm,"Identifier")); |
| assert(isIdent(exprTerm,"Expression")); |
| |
| char *ruleName = identifierString(builder,identTerm); |
| Expression *ruleExpr = buildExpression(builder,exprTerm); |
| GrammarDefine(builder->gram,ruleName,ruleExpr); |
| free(ruleName); |
| } |
| |
| GrammarResolve(builder->gram); |
| } |
| |
| // This function creates a new Grammar object from the result of parsing a file usin the built-in |
| // PEG grammar. The resulting Grammar object can then be used to parse other files which are written |
| // in another language that is accepted by that grammar. The Term objects are constructed by the |
| // parse function defined in Parser.c. |
| |
| Grammar *grammarFromTerm(Term *term, const char *input) |
| { |
| Grammar *gram = GrammarNew(); |
| |
| Builder *builder = (Builder *)calloc(1,sizeof(Builder)); |
| builder->gram = gram; |
| builder->input = input; |
| builder->len = strlen(input); |
| |
| buildGrammar(builder,term); |
| |
| free(builder); |
| |
| return gram; |
| } |
