oc.py 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
  1. # oc.py
  2. #
  3. # A subset-C parser, (BNF taken from 1996 International Obfuscated C Code Contest)
  4. #
  5. # Copyright, 2010, Paul McGuire
  6. #
  7. """
  8. https://www.ioccc.org/1996/august.hint
  9. The following is a description of the OC grammar:
  10. OC grammar
  11. ==========
  12. Terminals are in quotes, () is used for bracketing.
  13. program: decl*
  14. decl: vardecl
  15. fundecl
  16. vardecl: type NAME ;
  17. type NAME "[" INT "]" ;
  18. fundecl: type NAME "(" args ")" "{" body "}"
  19. args: /*empty*/
  20. ( arg "," )* arg
  21. arg: type NAME
  22. body: vardecl* stmt*
  23. stmt: ifstmt
  24. whilestmt
  25. dowhilestmt
  26. "return" expr ";"
  27. expr ";"
  28. "{" stmt* "}"
  29. ";"
  30. ifstmt: "if" "(" expr ")" stmt
  31. "if" "(" expr ")" stmt "else" stmt
  32. whilestmt: "while" "(" expr ")" stmt
  33. dowhilestmt: "do" stmt "while" "(" expr ")" ";"
  34. expr: expr binop expr
  35. unop expr
  36. expr "[" expr "]"
  37. "(" expr ")"
  38. expr "(" exprs ")"
  39. NAME
  40. INT
  41. CHAR
  42. STRING
  43. exprs: /*empty*/
  44. (expr ",")* expr
  45. binop: "+" | "-" | "*" | "/" | "%" |
  46. "=" |
  47. "<" | "==" | "!="
  48. unop: "!" | "-" | "*"
  49. type: "int" stars
  50. "char" stars
  51. stars: "*"*
  52. """
  53. from pyparsing import *
  54. ParserElement.enablePackrat()
  55. LPAR,RPAR,LBRACK,RBRACK,LBRACE,RBRACE,SEMI,COMMA = map(Suppress, "()[]{};,")
  56. INT, CHAR, WHILE, DO, IF, ELSE, RETURN = map(Keyword,
  57. "int char while do if else return".split())
  58. NAME = Word(alphas+"_", alphanums+"_")
  59. integer = Regex(r"[+-]?\d+")
  60. char = Regex(r"'.'")
  61. string_ = dblQuotedString
  62. TYPE = Group((INT | CHAR) + ZeroOrMore("*"))
  63. expr = Forward()
  64. func_call = Group(NAME + LPAR + Group(Optional(delimitedList(expr))) + RPAR)
  65. operand = func_call | NAME | integer | char | string_
  66. expr <<= (infixNotation(operand,
  67. [
  68. (oneOf('! - *'), 1, opAssoc.RIGHT),
  69. (oneOf('++ --'), 1, opAssoc.RIGHT),
  70. (oneOf('++ --'), 1, opAssoc.LEFT),
  71. (oneOf('* / %'), 2, opAssoc.LEFT),
  72. (oneOf('+ -'), 2, opAssoc.LEFT),
  73. (oneOf('< == > <= >= !='), 2, opAssoc.LEFT),
  74. (Regex(r'(?<!=)=(?!=)'), 2, opAssoc.LEFT),
  75. ]) +
  76. Optional( LBRACK + expr + RBRACK |
  77. LPAR + Group(Optional(delimitedList(expr))) + RPAR )
  78. )
  79. stmt = Forward()
  80. ifstmt = IF - LPAR + expr + RPAR + stmt + Optional(ELSE + stmt)
  81. whilestmt = WHILE - LPAR + expr + RPAR + stmt
  82. dowhilestmt = DO - stmt + WHILE + LPAR + expr + RPAR + SEMI
  83. returnstmt = RETURN - expr + SEMI
  84. stmt << Group( ifstmt |
  85. whilestmt |
  86. dowhilestmt |
  87. returnstmt |
  88. expr + SEMI |
  89. LBRACE + ZeroOrMore(stmt) + RBRACE |
  90. SEMI)
  91. vardecl = Group(TYPE + NAME + Optional(LBRACK + integer + RBRACK)) + SEMI
  92. arg = Group(TYPE + NAME)
  93. body = ZeroOrMore(vardecl) + ZeroOrMore(stmt)
  94. fundecl = Group(TYPE + NAME + LPAR + Optional(Group(delimitedList(arg))) + RPAR +
  95. LBRACE + Group(body) + RBRACE)
  96. decl = fundecl | vardecl
  97. program = ZeroOrMore(decl)
  98. program.ignore(cStyleComment)
  99. # set parser element names
  100. for vname in ("ifstmt whilestmt dowhilestmt returnstmt TYPE "
  101. "NAME fundecl vardecl program arg body stmt".split()):
  102. v = vars()[vname]
  103. v.setName(vname)
  104. #~ for vname in "fundecl stmt".split():
  105. #~ v = vars()[vname]
  106. #~ v.setDebug()
  107. test = r"""
  108. /* A factorial program */
  109. int
  110. putstr(char *s)
  111. {
  112. while(*s)
  113. putchar(*s++);
  114. }
  115. int
  116. fac(int n)
  117. {
  118. if (n == 0)
  119. return 1;
  120. else
  121. return n*fac(n-1);
  122. }
  123. int
  124. putn(int n)
  125. {
  126. if (9 < n)
  127. putn(n / 10);
  128. putchar((n%10) + '0');
  129. }
  130. int
  131. facpr(int n)
  132. {
  133. putstr("factorial ");
  134. putn(n);
  135. putstr(" = ");
  136. putn(fac(n));
  137. putstr("\n");
  138. }
  139. int
  140. main()
  141. {
  142. int i;
  143. i = 0;
  144. if(a() == 1){}
  145. while(i < 10)
  146. facpr(i++);
  147. return 0;
  148. }
  149. """
  150. ast = program.parseString(test, parseAll=True)
  151. ast.pprint()