/** | |
* <copyright> | |
* | |
* Copyright (c) 2012 E.D.Willink and others. | |
* All rights reserved. This program and the accompanying materials | |
* are made available under the terms of the Eclipse Public License v1.0 | |
* which accompanies this distribution, and is available at | |
* http://www.eclipse.org/legal/epl-v10.html | |
* | |
* Contributors: | |
* E.D.Willink - initial API and implementation | |
* | |
* </copyright> | |
*/ | |
/* | |
http://lampwww.epfl.ch/teaching/archive/compilation-ssc/2000/part4/parsing/node3.html | |
For building parsers (especially bottom-up) a BNF grammar is often better, than EBNF. But it's easy to convert an XBNF Grammar to XBNF: | |
Convert every repetition { E } to a fresh non-terminal X and add | |
X = $\epsilon$ | X E. | |
Convert every option [ E ] to a fresh non-terminal X and add | |
X = $\epsilon$ | E. | |
(We can convert X = A [ E ] B. to X = A E B | A B.) | |
Convert every group ( E ) to a fresh non-terminal X and add | |
X = E. | |
We can even do away with alternatives by having several productions with the same non-terminal. | |
X = E | E'. becomes X = E. X = E'. | |
--- | |
As above, also normalizse so that the output is a | |
rule comprising | |
-- a disjunction of | |
-- one or more conjunctions comprising | |
-- zero or more elements. | |
Additional rules for multiplicities and alternatives are created as sub-rules, some | |
of which may be inlined by a subsequent inline transformation. | |
*/ | |
modeltype ECORE uses 'http://www.eclipse.org/emf/2002/Ecore'; | |
modeltype XBNF uses 'http://www.eclipse.org/ocl/XBNF'; | |
modeltype XBNFwc uses 'http://www.eclipse.org/ocl/XBNFwithCardinality'; | |
transformation normalize(in xtext : XBNFwc, out XBNF); | |
main() { | |
xtext.rootObjects()[XBNF::Syntax]->map syntax2syntax(); | |
} | |
mapping XBNF::Syntax::syntax2syntax() : XBNF::Syntax { | |
var allRules : Sequence(TypedRule) = self.grammars->collect(rules->sortedBy(name)); | |
var firstRules : OrderedSet(TypedRule) = allRules->collect(r1 | allRules->select(r2 | r1.name = r2.name)->first())->asOrderedSet(); | |
name := self.name; | |
grammars := Sequence { self.map grammars2lexerGrammar(firstRules), self.map grammars2parserGrammar(firstRules) }; | |
} | |
--mapping XBNF::Grammar::grammar2grammar() : XBNF::Grammar | |
--disjuncts | |
--LexerGrammar::lexerGrammar2grammar, | |
--ParserGrammar::parserGrammar2grammar | |
--{} | |
--------------------------------------------------------------------------------------- | |
-- Copy the lexer rules | |
--------------------------------------------------------------------------------------- | |
mapping XBNF::Syntax::grammars2lexerGrammar(firstRules : Set(TypedRule)) : XBNF::LexerGrammar { | |
name := self.name; | |
rules := self.grammars.rules->select(oclIsKindOf(TerminalRule)).oclAsType(TerminalRule)->map terminalRule2rule(firstRules); | |
goals := self.grammars.goals.resolveone(TypedRule); | |
} | |
--mapping XBNF::LexerGrammar::lexerGrammar2grammar() : XBNF::LexerGrammar { | |
-- name := self.name; | |
-- rules := self.rules->select(oclIsKindOf(TerminalRule)).oclAsType(TerminalRule)->map terminalRule2rule(); | |
-- goals := self.goals.resolveone(TypedRule); | |
--} | |
mapping XBNF::TerminalRule::terminalRule2rule(firstRules : Set(TypedRule)) : XBNF::TerminalRule | |
{ | |
var subRules : List(XBNF::UntypedRule) = List{}; | |
name := self.name; | |
debug := self.debug; | |
type := self.type; | |
element := self.element.map element2element(self.name, subRules, self, firstRules); | |
subrules := subRules->iterate(r; acc : Sequence(XBNF::UntypedRule) = Sequence{} | acc->append(r)); | |
} | |
/* | |
mapping XBNF::AbstractElement::element2lexerElement() : XBNF::AbstractElement | |
disjuncts | |
Alternatives::alternatives2lexerElement, | |
CharacterRange::keyword2lexerElement, | |
Keyword::keyword2lexerElement, | |
NegatedToken::negatedToken2lexerElement, | |
OneOrMore::oneOrMore2lexerElement, | |
RuleCall::ruleCall2lexerElement, | |
Succession::succession2lexerElement, | |
UntilToken::untilToken2lexerElement, | |
Wildcard::wildcard2lexerElement, | |
ZeroOrMore::zeroOrMore2lexerElement, | |
ZeroOrOne::zeroOrOne2lexerElement, | |
AbstractElement::element2lexerElement_default | |
{} | |
mapping XBNF::AbstractElement::element2lexerElement_default() : XBNF::Wildcard { | |
debug := 'default'; | |
} | |
mapping XBNFwc::Alternatives::alternatives2lexerElement() : XBNFwc::Alternatives { | |
debug := self.debug; | |
elements := self.elements->map element2lexerElement(); | |
} | |
mapping XBNF::CharacterRange::keyword2lexerElement() : XBNF::CharacterRange { | |
debug := self.debug; | |
left := self.left; | |
right := self.right; | |
} | |
mapping XBNF::Keyword::keyword2lexerElement() : XBNF::Keyword { | |
debug := self.debug; | |
value := self.value; | |
} | |
mapping XBNF::NegatedToken::negatedToken2lexerElement() : XBNF::UntilToken { | |
debug := self.debug; | |
terminal := self.terminal.map element2lexerElement(); | |
} | |
mapping XBNFwc::OneOrMore::oneOrMore2lexerElement() : XBNFwc::Succession { | |
debug := self.debug; | |
elements := self.elements->map element2lexerElement(); | |
} | |
mapping XBNF::RuleCall::ruleCall2lexerElement() : XBNF::RuleCall { | |
debug := self.rule.name; | |
rule := self.rule.late resolveone(XBNF::AbstractRule); | |
} | |
mapping XBNFwc::Succession::succession2lexerElement() : XBNFwc::Succession { | |
debug := self.debug; | |
elements := self.elements->map element2lexerElement(); | |
} | |
mapping XBNF::UntilToken::untilToken2lexerElement() : XBNF::UntilToken { | |
debug := self.debug; | |
terminal := self.terminal.map element2lexerElement(); | |
} | |
mapping XBNF::Wildcard::wildcard2lexerElement() : XBNF::Wildcard { | |
debug := self.debug; | |
} | |
mapping XBNFwc::ZeroOrMore::zeroOrMore2lexerElement() : XBNFwc::Succession { | |
debug := self.debug; | |
elements := self.elements->map element2lexerElement(); | |
} | |
mapping XBNFwc::ZeroOrOne::zeroOrOne2lexerElement() : XBNFwc::Succession { | |
debug := self.debug; | |
elements := self.elements->map element2lexerElement(); | |
} | |
*/ | |
--------------------------------------------------------------------------------------- | |
-- Create the extra parser rules for XBNF compounds | |
--------------------------------------------------------------------------------------- | |
mapping XBNF::Syntax::grammars2parserGrammar(firstRules : Set(TypedRule)) : XBNF::ParserGrammar { | |
name := self.name; | |
-- var parserRules : Sequence(ParserRule) = self.grammars.rules->asSequence()->select(oclIsKindOf(ParserRule)).oclAsType(ParserRule); | |
-- var parserRuleNames : Set(String) = parserRules.name->asSet()->sortedBy(n | n); | |
-- rules := parserRuleNames->iterate(n; acc : OrderedSet(ParserRule) = Set{} | | |
-- let firstRule : ParserRule = parserRules->select(name = n)->first() in | |
-- let mappedRule : ParserRule = firstRule.map parserRule2rule() in | |
-- acc->append(mappedRule)); | |
var parserRules : Sequence(ParserRule) = self.grammars.rules->select(oclIsKindOf(ParserRule)).oclAsType(ParserRule); | |
var parserRuleNames : OrderedSet(String) = parserRules.name->asSet()->sortedBy(n | n); | |
var sortedParserRules : Sequence(ParserRule) = parserRules->sortedBy(name); | |
rules := parserRuleNames->iterate(prn; acc : OrderedSet(ParserRule) = OrderedSet{} | | |
let pr : ParserRule = parserRules->select(name = prn)->any(true) in acc->append(pr.map parserRule2rule(firstRules))); | |
-- rules := sortedParserRules->iterate(pr; acc : Sequence(ParserRule) = Sequence{} | acc->append(pr.map parserRule2rule())); | |
goals := self.grammars->select(oclIsKindOf(ParserGrammar)).goals->first().resolveone(TypedRule); | |
} | |
--mapping XBNF::ParserGrammar::parserGrammar2grammar() : XBNF::ParserGrammar { | |
-- name := self.name; | |
-- var parserRules : Sequence(ParserRule) = self.rules->select(oclIsKindOf(ParserRule)).oclAsType(ParserRule)->sortedBy(name); | |
-- rules := parserRules->map parserRule2rule(); | |
-- goals := self.goals.resolveone(TypedRule); | |
--} | |
mapping XBNF::ParserRule::parserRule2rule(firstRules : Set(TypedRule)) : XBNF::ParserRule | |
{ | |
var subRules : List(XBNF::UntypedRule) = List{}; | |
var theElement : AbstractElement = self.element.map element2element(self.name, subRules, self, firstRules); | |
var disjunction : Disjunction = | |
if theElement.oclIsKindOf(Disjunction) | |
then theElement.oclAsType(Disjunction) | |
else object Disjunction { | |
conjunctions := Sequence { | |
if theElement.oclIsKindOf(Conjunction) | |
then theElement.oclAsType(Conjunction) | |
else object Conjunction { | |
elements := theElement->asSequence(); | |
} | |
endif | |
}; | |
} | |
endif; | |
name := self.name; | |
debug := self.debug; | |
type := self.type; | |
element := disjunction; | |
subrules := subRules->iterate(r; acc : Sequence(XBNF::UntypedRule) = Sequence{} | acc->append(r)); | |
} | |
mapping XBNF::AbstractElement::element2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::AbstractElement | |
disjuncts | |
ActionAssignment::actionAssignment2element, | |
Alternatives::alternativesAtRoot2element, | |
Alternatives::alternativesNested2element, | |
CharacterRange::characterRange2element, | |
KeywordAssignment::keywordAssignment2element, | |
Keyword::keyword2element, | |
NegatedToken::negatedToken2element, | |
OneOrMore::oneOrMore2element, | |
RuleCallAssignment::ruleCallAssignment2element, | |
RuleCall::ruleCall2element, | |
Succession::succession2element, | |
UntilToken::untilToken2element, | |
Wildcard::wildcard2element, | |
ZeroOrMore::zeroOrMore2element, | |
ZeroOrOne::zeroOrOne2element, | |
AbstractElement::element2element_default | |
{} | |
mapping XBNF::AbstractElement::element2element_default(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::Wildcard { | |
debug := 'default'; | |
} | |
mapping XBNF::ActionAssignment::actionAssignment2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::ActionAssignment { | |
debug := self.debug; | |
feature := self.feature; | |
operator := self.operator; | |
type := self.type; | |
} | |
mapping XBNFwc::Alternatives::alternativesAtRoot2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::Disjunction | |
when { self.parentRule <> null } | |
{ | |
debug := self.debug; | |
conjunctions := self.elements->iterate(e; acc : Sequence(Conjunction) = Sequence {} | | |
acc->append(object Conjunction { | |
elements := e.succession(Sequence{}, e)->map element2element(parentRule, subRules, disambiguator, firstRules) | |
})); | |
} | |
mapping XBNFwc::Alternatives::alternativesNested2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCall | |
{ | |
var me : Alternatives = self; | |
var alternatives : Sequence(AbstractElement) = self.elements; | |
var oneRule : XBNF::UntypedRule = object UntypedRule { | |
element := object Disjunction { | |
debug := '1 : ' + alternatives->size().toString(); | |
conjunctions := alternatives->iterate(e; acc : Sequence(Conjunction) = Sequence{} | | |
acc->append(object Conjunction { | |
elements := e.succession(Sequence{}, e)->map element2element(parentRule, subRules, e, firstRules); | |
})); | |
}; | |
name := parentRule + '_' + subRules->size().toString(); | |
}; | |
subRules->add(oneRule); | |
debug := oneRule.name; | |
referredRule := oneRule; | |
} | |
mapping XBNF::CharacterRange::characterRange2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::CharacterRange { | |
debug := self.debug; | |
left := self.left; | |
right := self.right; | |
} | |
mapping XBNF::Keyword::keyword2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::Keyword { | |
debug := self.debug; | |
value := self.value; | |
} | |
mapping XBNF::KeywordAssignment::keywordAssignment2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::KeywordAssignment { | |
debug := self.debug; | |
feature := self.feature; | |
operator := self.operator; | |
value := self.value; | |
} | |
mapping XBNF::NegatedToken::negatedToken2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::UntilToken { | |
debug := self.debug; | |
terminal := self.terminal.map element2element(parentRule, subRules, disambiguator, firstRules); | |
} | |
mapping XBNFwc::OneOrMore::oneOrMore2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCall { | |
var oneRule : XBNF::UntypedRule = self.map element2subRule(parentRule, subRules, disambiguator, firstRules); | |
subRules->add(oneRule); | |
var oneOrMoreRule : XBNF::UntypedRule = oneRule.map rule2oneOrMoreSubRule(parentRule, subRules); | |
subRules->add(oneOrMoreRule); | |
debug := oneOrMoreRule.name; | |
referredRule := oneOrMoreRule; | |
} | |
mapping XBNF::RuleCall::ruleCall2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCall { | |
debug := self.debug; | |
referredRule := firstRules->select(r | r.name = self.referredRule.name)->any(true).late resolveone(XBNF::AbstractRule); | |
} | |
mapping XBNF::RuleCallAssignment::ruleCallAssignment2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCallAssignment { | |
-- var syntax : Syntax = self.referredRule.grammar.syntax; | |
debug := self.debug; | |
feature := self.feature; | |
operator := self.operator; | |
referredRule := firstRules->select(r | r.name = self.referredRule.name)->any(true).late resolveone(XBNF::AbstractRule); | |
} | |
mapping XBNFwc::Succession::succession2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::Conjunction { | |
debug := self.debug; | |
elements := self.succession(Sequence{}, self)->map element2element(parentRule, subRules, disambiguator, firstRules); | |
} | |
mapping XBNF::UntilToken::untilToken2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::UntilToken { | |
debug := self.debug; | |
terminal := self.terminal.map element2element(parentRule, subRules, disambiguator, firstRules); | |
} | |
mapping XBNF::Wildcard::wildcard2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::Wildcard { | |
debug := self.debug; | |
} | |
mapping XBNFwc::ZeroOrMore::zeroOrMore2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCall { | |
var oneRule : UntypedRule = self.map element2subRule(parentRule, subRules, disambiguator, firstRules); | |
subRules->add(oneRule); | |
var oneOrMoreRule : UntypedRule = oneRule.map rule2oneOrMoreSubRule(parentRule, subRules); | |
subRules->add(oneOrMoreRule); | |
var zeroOrMoreRule : UntypedRule = object UntypedRule { | |
element := object Disjunction { | |
debug := '0 or +'; | |
conjunctions := Sequence { | |
object Conjunction { | |
elements := Sequence { | |
object XBNF::Epsilon {} | |
}; | |
}, | |
object Conjunction { | |
elements := Sequence { | |
object XBNF::RuleCall { | |
debug := oneOrMoreRule.name; | |
referredRule := oneOrMoreRule; | |
} | |
}; | |
} | |
}; | |
}; | |
name := parentRule + '_' + subRules->size().toString(); | |
}; | |
subRules->add(zeroOrMoreRule); | |
debug := zeroOrMoreRule.name; | |
referredRule := zeroOrMoreRule | |
} | |
mapping XBNFwc::ZeroOrOne::zeroOrOne2element(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::RuleCall { | |
var me : CompoundElement = self; | |
var alternatives : Sequence(AbstractElement) = self.elements; | |
var zeroOrOneRule : UntypedRule = object UntypedRule { | |
element := object Disjunction { | |
debug := '0 or 1'; | |
conjunctions := alternatives->iterate(e; acc : Sequence(Conjunction) = Sequence { | |
object Conjunction { | |
elements := Sequence { | |
object XBNF::Epsilon {} | |
}; | |
} | |
} | | |
acc->append(object Conjunction { | |
elements := e.succession(Sequence{}, e)->map element2element(parentRule, subRules, e, firstRules); | |
})); | |
}; | |
name := parentRule + '_' + subRules->size().toString(); | |
}; | |
subRules->add(zeroOrOneRule); | |
debug := zeroOrOneRule.name; | |
referredRule := zeroOrOneRule | |
} | |
-- Helpers | |
mapping XBNFwc::CompoundElement::element2subRule(parentRule : String, subRules : List(XBNF::UntypedRule), disambiguator : OclAny, firstRules : Set(TypedRule)) : XBNF::UntypedRule { | |
var me : CompoundElement = self; | |
var alternatives : Sequence(AbstractElement) = self.elements; | |
element := object Disjunction { | |
debug := '1'; | |
conjunctions := alternatives->iterate(e; acc : Sequence(Conjunction) = Sequence{} | | |
acc->append(object Conjunction { | |
elements := e.succession(Sequence{}, e)->map element2element(parentRule, subRules, e, firstRules); | |
})); | |
}; | |
name := parentRule + '_' + subRules->size().toString(); | |
} | |
mapping XBNF::AbstractRule::rule2oneOrMoreSubRule(parentRule : String, subRules : List(XBNF::UntypedRule)) : XBNF::UntypedRule { | |
name := parentRule + '_' + subRules->size().toString(); | |
element := object Disjunction { | |
debug := '1 or +'; | |
conjunctions := Sequence { | |
object Conjunction { | |
elements := Sequence { | |
object RuleCall { | |
debug := self.name; | |
referredRule := self; | |
} | |
}; | |
}, | |
object Conjunction { | |
elements := Sequence { | |
object XBNF::RuleCall { | |
debug := result.name; | |
referredRule := result; | |
}, | |
object XBNF::RuleCall { | |
debug := self.name; | |
referredRule := self; | |
} | |
}; | |
} | |
}; | |
}; | |
} | |
--------------------------------------------------------------------------------------- | |
-- Return an in-order sequence of flattened terms. | |
--------------------------------------------------------------------------------------- | |
helper XBNF::AbstractElement::succession(head : Sequence(AbstractElement), disambiguator : OclAny) : Sequence(AbstractElement) | |
{ | |
return head->append(self); | |
} | |
helper XBNFwc::Succession::succession(head : Sequence(AbstractElement), disambiguator : OclAny) : Sequence(AbstractElement) | |
{ | |
return self.elements->iterate(e; acc : Sequence(AbstractElement) = head | e.succession(acc, disambiguator)); | |
} | |