1 /*

     2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description:

    15 *

    16 */

    17 #include "CoreParser.h"

    18 #include <sstream>

    19 #include <iostream>

    20 using namespace std;

    21 

    22 

    23 ParseResult::ParseResult()

    24 : iRuleId(0), iStart(0), iEnd(0)

    25 	{

    26 	}

    27 

    28 bool ParseResult::Matched() const

    29 	{

    30 	return iRuleId != 0;

    31 	}

    32 

    33 ParseResult ParseResult::Fail()

    34 	{

    35 	ParseResult p;

    36 	return p;

    37 	}

    38 

    39 

    40 Parser::Parser()

    41 : iOp(ENul), iMatch(0), iSub1(0), iSub2(0), iId(-1)

    42 	{

    43 	}

    44 

    45 Parser::Parser(const char* aMatch)

    46 : iOp(EExact), iMatch(aMatch), iSub1(0), iSub2(0), iId(-1)

    47 	{

    48 	}

    49 

    50 Parser::Parser(T0Op aOp)

    51 : iOp(aOp), iMatch(0), iSub1(0), iSub2(0), iId(-1)

    52 	{

    53 	}

    54 

    55 Parser::Parser(T1Op aOp, const Parser& aSub)

    56 : iOp(aOp), iMatch(0), iSub1(&aSub), iSub2(0), iId(-1)

    57 	{

    58 	}

    59 

    60 Parser::Parser(T2Op aOp, const Parser& aFirst, const Parser& aRest)

    61 : iOp(aOp), iMatch(0), iSub1(&aFirst), iSub2(&aRest), iId(-1)

    62 	{

    63 	}

    64 

    65 Parser::Parser(const Parser& aOther)

    66 	{

    67 	*this = aOther;

    68 	}

    69 

    70 const Parser& Parser::operator=(const Parser& aOther)

    71 	{

    72 	if (this == &aOther)

    73 		return *this;

    74 

    75 	iOp = aOther.iOp;

    76 	iMatch = aOther.iMatch;

    77 	iSub1 = 0;

    78 	iSub2 = 0;

    79 	iSub1 = aOther.iSub1;

    80 	iSub2 = aOther.iSub2;

    81 	iId = aOther.iId;

    82 //	if (aOther.iSub1)

    83 //		iSub1 = new Parser(*aOther.iSub1);

    84 //	if (aOther.iSub2)

    85 //		iSub2 = new Parser(*aOther.iSub2);

    86 

    87 	return *this;

    88 	}

    89 

    90 Parser::~Parser()

    91 	{

    92 //	delete iSub1;

    93 //	delete iSub2;

    94 	}

    95 

    96 Parser Parser::EOS()

    97 	{

    98 	return Parser(EEos);

    99 	}

   100 

   101 Parser Parser::Int()

   102 	{

   103 	return Parser(EInt);

   104 	}

   105 

   106 Parser Parser::Real()

   107 	{

   108 	return Parser(EReal);

   109 	}

   110 

   111 const Parser& Parser::Nul()

   112 	{

   113 	static Parser nul(ENul);

   114 	nul.SetId(0);

   115 	return nul;

   116 	}

   117 

   118 

   119 ParseResult Parser::Parse(const std::string& aString) const

   120 	{

   121 	vector<Step> stack;

   122 	stack.push_back(Step(this, 0, -1));

   123 	TMatchRes res = EContinue;

   124 	bool done = false;

   125 

   126 	while (!stack.empty() && !done)

   127 		{

   128 		Step& top = stack.back();

   129 		int topId = stack.size()-1;

   130 		switch (res)

   131 			{

   132 			case EFail:

   133 				if (top.iRule->iOp == EAlt && top.iStep < 2)

   134 					{

   135 					res = top.iRule->ParseStep(topId, aString, top.iPos, stack);

   136 					}

   137 				else if (top.iRule->iOp == EMult && top.iStep < 2)

   138 					{

   139 					top.iStep = 2;

   140 					res = top.iRule->ParseStep(topId, aString, top.iPos, stack);

   141 					}

   142 				else

   143 					{

   144 					if (top.iParent >= 0 && stack[top.iParent].iRule->iOp == ESeq)

   145 						stack[top.iParent].iStep--;

   146 					stack.pop_back();

   147 					}

   148 				break;

   149 

   150 			case EPass:

   151 				{

   152 				int nextSeq = -1;

   153 				for (int i=stack.size()-1; nextSeq==-1 && i>=0; i--)

   154 					{

   155 					if ((stack[i].iRule->iOp == ESeq && stack[i].iStep < 2) || 

   156 						(stack[i].iRule->iOp == EMult && stack[i].iStep < 3))

   157 						nextSeq = i;

   158 					}

   159 				if (nextSeq >= 0)

   160 					res = stack[nextSeq].iRule->ParseStep(nextSeq, aString, top.iResult.iEnd, stack);

   161 				else

   162 					done = true;

   163 				break;

   164 				}

   165 

   166 			case EContinue:

   167 				res = top.iRule->ParseStep(topId, aString, top.iPos, stack);

   168 				break;

   169 			}

   170 		}

   171 

   172 	if (done)

   173 		{

   174 		for (int i=stack.size()-1; i>=1; i--)

   175 			{

   176 			Step& step = stack[i];

   177 			Step& parent = stack[step.iParent];

   178 			parent.iResult.iChildren.push_front(step.iResult);

   179 			if (parent.iResult.iEnd < step.iResult.iEnd)

   180 				parent.iResult.iEnd = step.iResult.iEnd;

   181 			}

   182 

   183 		return stack[0].iResult;

   184 		}

   185 	else

   186 		return ParseResult::Fail();

   187 	}

   188 

   189 Parser::TMatchRes Parser::ParseStep(int aStepId, const std::string& aString, int aPos, vector<Step>& aStack) const

   190 	{

   191 	Step& step = aStack[aStepId];

   192 	step.iResult.iRuleId = Id();

   193 	

   194 	switch (iOp)

   195 		{

   196 		case EExact:

   197 			{

   198 			string match(iMatch);

   199 			int mLen = match.size();

   200 			if (mLen + aPos > aString.size())

   201 				return EFail;

   202 			else if (aString.substr(aPos, mLen) != match)

   203 				return EFail;

   204 			else

   205 				step.iResult.iEnd = aPos + mLen;

   206 			return EPass;

   207 			}

   208 

   209 		case EEos:

   210 			{

   211 			if (aPos != aString.size())

   212 				return EFail;

   213 			else

   214 				step.iResult.iEnd = aPos;

   215 			return EPass;

   216 			}

   217 

   218 		case EInt:

   219 			{

   220 			istringstream strm(aString.substr(aPos));

   221 			int temp;

   222 			strm >> temp;

   223 			int len = strm.tellg();

   224 			if (len >= 0)

   225 				step.iResult.iEnd = aPos + len;

   226 			else

   227 				return EFail;

   228 			return EPass;

   229 			}

   230 

   231 		case EReal:

   232 			{

   233 			istringstream strm(aString.substr(aPos));

   234 			double temp;

   235 			strm >> temp;

   236 			int len = strm.tellg();

   237 			if (len >= 0)

   238 				step.iResult.iEnd = aPos + len;

   239 			else

   240 				return EFail;

   241 			return EPass;

   242 			}

   243 

   244 		case ENul:

   245 			{

   246 			step.iResult.iChildren.clear();

   247 			step.iResult.iEnd = aPos;

   248 			return EPass;

   249 			}

   250 

   251 		case EMult:

   252 			{

   253 /*			Step next(iSub1, aPos, aStepId);

   254 			if (step.iStep == 1)

   255 				next.iRule = this;

   256 			else if (step.iStep == 2)

   257 				next.iRule = &Parser::Nul();

   258 			step.iStep++;

   259 			aStack.push_back(next);

   260 			return EContinue;

   261 */

   262 			return EFail;

   263 			}

   264 

   265 		case ESeq:

   266 			{

   267 			Step next(iSub1, aPos, aStepId);

   268 			if (step.iStep == 1)

   269 				next.iRule = iSub2;

   270 			step.iStep++;

   271 			aStack.push_back(next);

   272 			return EContinue;

   273 			}

   274 

   275 		case EAlt:

   276 			{

   277 			Step next(iSub1, aPos, aStepId);

   278 			if (step.iStep == 1)

   279 				next.iRule = iSub2;

   280 			step.iStep++;

   281 			aStack.push_back(next);

   282 			return EContinue;

   283 			}

   284 		}

   285 

   286 	return EFail;

   287 	}

   288 

   289 int Parser::Id() const

   290 	{

   291 	return iId;

   292 	}

   293 

   294 void Parser::SetId(int aId)

   295 	{

   296 	iId = aId;

   297 	}

   298 

   299 

   300 Parser operator|(const Parser& aFirst, const Parser& aRest)

   301 	{

   302 	return Parser(Parser::EAlt, aFirst, aRest);

   303 	}

   304 

   305 Parser operator>>(const Parser& aFirst, const Parser& aRest)

   306 	{

   307 	return Parser(Parser::ESeq, aFirst, aRest);

   308 	}

   309 

   310 /*Parser operator*(const Parser& aSub)

   311 	{

   312 	return Parser(Parser::EMult, aSub);

   313 	}

   314 */

   315 

   316 void DoPrint(const ParseResult& res)

   317 	{

   318 	cout << res.iRuleId << " " << res.iStart << "..." << res.iEnd << " ";

   319 	if (res.iChildren.size())

   320 		{

   321 		cout << "{ ";

   322 		for (int i=0; i<res.iChildren.size(); i++)

   323 			DoPrint(res.iChildren[i]);

   324 		cout << "} ";

   325 		}

   326 	}

   327 

   328 void Print(const ParseResult& res)

   329 	{

   330 	DoPrint(res);

   331 	cout << endl;

   332 	}

   333 

   334 int TestParser()

   335 	{

   336 	Parser p = Parser("A");

   337 	ParseResult res;

   338 	res = p.Parse("A");	Print(res);

   339 	res = p.Parse("B");	Print(res);

   340 

   341 	p = Parser("A") | Parser("B");

   342 	res = p.Parse("A");	Print(res);

   343 	res = p.Parse("B");	Print(res);

   344 	res = p.Parse("AB"); Print(res);

   345 	res = p.Parse("C");	Print(res);

   346 

   347 	p = Parser("A") | Parser("B") | Parser("C");

   348 	res = p.Parse("A");	Print(res);

   349 	res = p.Parse("B");	Print(res);

   350 	res = p.Parse("AB"); Print(res);

   351 	res = p.Parse("C");	Print(res);

   352 	res = p.Parse("D");	Print(res);

   353 

   354 	p = Parser("A") >> Parser("B");

   355 	res = p.Parse("A");	Print(res);

   356 	res = p.Parse("B"); Print(res);

   357 	res = p.Parse("AB"); Print(res);

   358 	res = p.Parse("BA"); Print(res);

   359 	res = p.Parse("C"); Print(res);

   360 

   361 	p = Parser("A") >> Parser("B") >> Parser("C");

   362 	res = p.Parse("A");	Print(res);

   363 	res = p.Parse("B"); Print(res);

   364 	res = p.Parse("AB"); Print(res);

   365 	res = p.Parse("ABC"); Print(res);

   366 	res = p.Parse("ABCD"); Print(res);

   367 	res = p.Parse("BAC"); Print(res);

   368 	res = p.Parse("D"); Print(res);

   369 

   370 	p = Parser("A") >> Parser("B") >> Parser("A") >> Parser::EOS();

   371 	res = p.Parse("A"); Print(res);

   372 	res = p.Parse("B"); Print(res);

   373 	res = p.Parse("AB"); Print(res);

   374 	res = p.Parse("BA"); Print(res);

   375 	res = p.Parse("ABA"); Print(res);

   376 	res = p.Parse("ABAB"); Print(res);

   377 	res = p.Parse("C"); Print(res);

   378 

   379 	p = (Parser("A") | Parser("B")) >> Parser("C");

   380 	res = p.Parse("A");	Print(res);

   381 	res = p.Parse("B"); Print(res);

   382 	res = p.Parse("AC"); Print(res);

   383 	res = p.Parse("BC"); Print(res);

   384 	res = p.Parse("BA"); Print(res);

   385 	res = p.Parse("C"); Print(res);

   386 	res = p.Parse("CC"); Print(res);

   387 

   388 	p = Parser("A") >> (Parser("B") | Parser("BB")) >> Parser::EOS();

   389 	res = p.Parse("A"); Print(res);

   390 	res = p.Parse("AB"); Print(res);

   391 	res = p.Parse("ABB"); Print(res);

   392 	res = p.Parse("ABBB"); Print(res);

   393 

   394 	p = Parser("A") >> (Parser("B") | Parser("C")) >> (Parser("D") | Parser("E")) >> Parser::EOS();

   395 	res = p.Parse("A"); Print(res);

   396 	res = p.Parse("AB"); Print(res);

   397 	res = p.Parse("AC"); Print(res);

   398 	res = p.Parse("AD"); Print(res);

   399 	res = p.Parse("AE"); Print(res);

   400 	res = p.Parse("ABD"); Print(res);

   401 	res = p.Parse("ABE"); Print(res);

   402 	res = p.Parse("ACD"); Print(res);

   403 	res = p.Parse("ACE"); Print(res);

   404 	res = p.Parse("ADB"); Print(res);

   405 	res = p.Parse("AEB"); Print(res);

   406 	res = p.Parse("ADC"); Print(res);

   407 	res = p.Parse("AEC"); Print(res);

   408 	res = p.Parse("ABDB"); Print(res);

   409 	res = p.Parse("ABEC"); Print(res);

   410 	res = p.Parse("ACDE"); Print(res);

   411 	res = p.Parse("ACEE"); Print(res);

   412 

   413 	p = Parser("A") | Parser("B");

   414 	Parser q = p >> p;

   415 	cout << p.Id() << endl;

   416 	cout << q.Id() << endl;

   417 	res = q.Parse("A"); Print(res);

   418 	res = q.Parse("B"); Print(res);

   419 	res = q.Parse("AA"); Print(res);

   420 	res = q.Parse("AB"); Print(res);

   421 	res = q.Parse("BA"); Print(res);

   422 	res = q.Parse("BB"); Print(res);

   423 	res = q.Parse("AC"); Print(res);

   424 	res = q.Parse("CA"); Print(res);

   425 

   426 	q = Parser("A") >> p;

   427 	p = q | Parser::Nul();

   428 	res = p.Parse("A"); Print(res);

   429 	res = p.Parse("B"); Print(res);

   430 	res = p.Parse("AA"); Print(res);

   431 	res = p.Parse(""); Print(res);

   432 

   433 	Parser r = Parser::Nul();

   434 	q = Parser("A") >> r;

   435 	r = q | Parser::Nul();

   436 	p = r >> Parser::EOS();

   437 	res = p.Parse("A"); Print(res);

   438 	res = p.Parse("B"); Print(res);

   439 	res = p.Parse("AA"); Print(res);

   440 	res = p.Parse("AAB"); Print(res);

   441 	res = p.Parse(""); Print(res);

   442 

   443 	p = Parser("B") >> r >> Parser("B");

   444 	res = p.Parse("B"); Print(res);

   445 	res = p.Parse("BB"); Print(res);

   446 	res = p.Parse("BAB"); Print(res);

   447 	res = p.Parse("BAAB"); Print(res);

   448 	res = p.Parse("BAAAB"); Print(res);

   449 

   450 	p = r >> Parser("AAB");

   451 	res = p.Parse("B"); Print(res);

   452 	res = p.Parse("AB"); Print(res);

   453 	res = p.Parse("AAB"); Print(res);

   454 	res = p.Parse("AAAB"); Print(res);

   455 	res = p.Parse("AAAAB"); Print(res);

   456 

   457 	p = Parser::Int();

   458 	res = p.Parse("1"); Print(res);

   459 	res = p.Parse("a"); Print(res);

   460 	res = p.Parse("123"); Print(res);

   461 	res = p.Parse("123ab"); Print(res);

   462 	res = p.Parse(""); Print(res);

   463 	

   464 	p = Parser::Real();

   465 	res = p.Parse("1"); Print(res);

   466 	res = p.Parse("1.0"); Print(res);

   467 	res = p.Parse(".01"); Print(res);

   468 	res = p.Parse("1e9"); Print(res);

   469 	res = p.Parse("a"); Print(res);

   470 	res = p.Parse("123"); Print(res);

   471 	res = p.Parse("123ab"); Print(res);

   472 	res = p.Parse(""); Print(res);

   473 	

   474 

   475 	// unsupported *

   476 /*	p = *Parser("A");

   477 	res = p.Parse("A"); Print(res);

   478 	res = p.Parse("B"); Print(res);

   479 	res = p.Parse("AA"); Print(res);

   480 	res = p.Parse(""); Print(res);

   481 

   482 	p = *Parser("A") >> Parser::EOS();

   483 	res = p.Parse("A"); Print(res);

   484 	res = p.Parse("B"); Print(res);

   485 	res = p.Parse("AA"); Print(res);

   486 	res = p.Parse("AAB"); Print(res);

   487 	res = p.Parse(""); Print(res);

   488 

   489 	p = Parser("B") >> *Parser("A") >> Parser("B");

   490 	res = p.Parse("B"); Print(res);

   491 	res = p.Parse("BB"); Print(res);

   492 	res = p.Parse("BAB"); Print(res);

   493 	res = p.Parse("BAAB"); Print(res);

   494 	res = p.Parse("BAAAB"); Print(res);

   495 

   496 	p = *Parser("A") >> Parser("AB");

   497 	res = p.Parse("B"); Print(res);

   498 	res = p.Parse("AB"); Print(res);

   499 	res = p.Parse("AAB"); Print(res);

   500 	res = p.Parse("AAAB"); Print(res);

   501 	res = p.Parse("AAAAB"); Print(res);

   502 */

   503 	return 0;

   504 	}

   505 /*

   506 Parser p = Parser("A") >> (Parser("B") | Parser("C")) >> (Parser("D") | Parser("E")) >> Parser("F");

   507 Parser q = p | (p >> q);

   508 int TestFormulaTreeNode()

   509 	{

   510 

   511 	ParseResult res;

   512 	res = q.Parse("ACEFACEF");	Print(res);

   513 	return 0;

   514 	}

   515 */

   516 // note, uncomment this line to execute test code

   517 //int x = TestParser();