pymicko.py 59 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387
  1. #!/usr/bin/python
  2. # Python/pyparsing educational microC compiler v1.0
  3. # Copyright (C) 2009 Zarko Zivanov
  4. # (largely based on flex/bison microC compiler by Zorica Suvajdzin, used with her permission;
  5. # current version can be found at http://www.acs.uns.ac.rs, under "Programski Prevodioci" [Serbian site])
  6. #
  7. # This program is free software: you can redistribute it and/or modify
  8. # it under the terms of the GNU General Public License as published by
  9. # the Free Software Foundation, either version 3 of the License, or
  10. # (at your option) any later version.
  11. #
  12. # This program is distributed in the hope that it will be useful,
  13. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15. # GNU General Public License for more details.
  16. #
  17. # A copy of the GNU General Public License can be found at <https://www.gnu.org/licenses/>.
  18. from pyparsing import *
  19. from sys import stdin, argv, exit
  20. #defines debug level
  21. # 0 - no debug
  22. # 1 - print parsing results
  23. # 2 - print parsing results and symbol table
  24. # 3 - print parsing results only, without executing parse actions (grammar-only testing)
  25. DEBUG = 0
  26. ##########################################################################################
  27. ##########################################################################################
  28. # About microC language and microC compiler
  29. # microC language and microC compiler are educational tools, and their goal is to show some basic principles
  30. # of writing a C language compiler. Compiler represents one (relatively simple) solution, not necessarily the best one.
  31. # This Python/pyparsing version is made using Python 2.6.4 and pyparsing 1.5.2 (and it may contain errors :) )
  32. ##########################################################################################
  33. ##########################################################################################
  34. # Model of the used hypothetical processor
  35. # The reason behind using a hypothetical processor is to simplify code generation and to concentrate on the compiler itself.
  36. # This compiler can relatively easily be ported to x86, but one must know all the little details about which register
  37. # can be used for what, which registers are default for various operations, etc.
  38. # The hypothetical processor has 16 registers, called %0 to %15. Register %13 is used for the function return value (x86's eax),
  39. # %14 is the stack frame pointer (x86's ebp) and %15 is the stack pointer (x86's esp). All data-handling instructions can be
  40. # unsigned (suffix U), or signed (suffix S). These are ADD, SUB, MUL and DIV. These are three-address instructions,
  41. # the first two operands are input, the third one is output. Whether these operands are registers, memory or constant
  42. # is not relevant, all combinations are possible (except that output cannot be a constant). Constants are writen with a $ prefix (10-base only).
  43. # Conditional jumps are handled by JXXY instructions, where XX is LT, GT, LE, GE, EQ, NE (less than, greater than, less than or equal, etc.)
  44. # and Y is U or S (unsigned or signed, except for JEQ i JNE). Unconditional jump is JMP. The move instruction is MOV.
  45. # Function handling is done using CALL, RET, PUSH and POP (C style function calls). Static data is defined using the WORD directive
  46. # (example: variable: WORD 1), whose only argument defines the number of locations that are reserved.
  47. ##########################################################################################
  48. ##########################################################################################
  49. # Grammar of The microC Programming Language
  50. # (small subset of C made for compiler course at Faculty of Technical Sciences, Chair for Applied Computer Sciences, Novi Sad, Serbia)
  51. # Patterns:
  52. # letter
  53. # -> "_" | "a" | "A" | "b" | "B" | "c" | "C" | "d" | "D" | "e" | "E" | "f"
  54. # | "F" | "g" | "G" | "h" | "H" | "i" | "I" | "j" | "J" | "k" | "K" | "l"
  55. # | "L" | "m" | "M" | "n" | "N" | "o" | "O" | "p" | "P" | "q" | "Q" | "r"
  56. # | "R" | "s" | "S" | "t" | "T" | "u" | "U" | "v" | "V" | "w" | "W" | "x"
  57. # | "X" | "y" | "Y" | "z" | "Z"
  58. # digit
  59. # -> "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
  60. # identifier
  61. # -> letter ( letter | digit )*
  62. # int_constant
  63. # -> digit +
  64. # unsigned_constant
  65. # -> digit + ( "u" | "U" )
  66. # Productions:
  67. # program
  68. # -> variable_list function_list
  69. # -> function_list
  70. # variable_list
  71. # -> variable ";"
  72. # -> variable_list variable ";"
  73. # variable
  74. # -> type identifier
  75. # type
  76. # -> "int"
  77. # -> "unsigned"
  78. # function_list
  79. # -> function
  80. # -> function_list function
  81. # function
  82. # -> type identifier "(" parameters ")" body
  83. # parameters
  84. # -> <empty>
  85. # -> parameter_list
  86. # parameter_list
  87. # -> variable
  88. # -> parameter_list "," variable
  89. # body
  90. # -> "{" variable_list statement_list "}"
  91. # -> "{" statement_list "}"
  92. # statement_list
  93. # -> <empty>
  94. # -> statement_list statement
  95. # statement
  96. # -> assignement_statement
  97. # -> function_call_statement
  98. # -> if_statement
  99. # -> while_statement
  100. # -> return_statement
  101. # -> compound_statement
  102. # assignement_statement
  103. # -> identifier "=" num_exp ";"
  104. # num_exp
  105. # -> mul_exp
  106. # -> num_exp "+" mul_exp
  107. # -> num_exp "-" mul_exp
  108. # mul_exp
  109. # -> exp
  110. # -> mul_exp "*" exp
  111. # -> mul_exp "/" exp
  112. # exp
  113. # -> constant
  114. # -> identifier
  115. # -> function_call
  116. # -> "(" num_exp ")"
  117. # -> "+" exp
  118. # -> "-" exp
  119. # constant
  120. # -> int_constant
  121. # -> unsigned_constant
  122. # function_call
  123. # -> identifier "(" arguments ")"
  124. # arguments
  125. # -> <empty>
  126. # -> argument_list
  127. # argument_list
  128. # -> num_exp
  129. # -> argument_list "," num_exp
  130. # function_call_statement
  131. # -> function_call ";"
  132. # if_statement
  133. # -> "if" "(" log_exp ")" statement
  134. # -> "if" "(" log_exp ")" statement "else" statement
  135. # -> -> -> -> -> -> -> -> 2
  136. # log_exp
  137. # -> and_exp
  138. # -> log_exp "||" and_exp
  139. # and_exp
  140. # -> rel_exp
  141. # -> and_exp "&&" rel_exp
  142. # rel_exp
  143. # -> num_exp "<" num_exp
  144. # -> num_exp ">" num_exp
  145. # -> num_exp "<=" num_exp
  146. # -> num_exp ">=" num_exp
  147. # -> num_exp "==" num_exp
  148. # -> num_exp "!=" num_exp
  149. # while_statement
  150. # -> "while" "(" log_exp ")" statement
  151. # return_statement
  152. # -> "return" num_exp ";"
  153. # compound_statement
  154. # -> "{" statement_list "}"
  155. # Comment: /* a comment */
  156. ##########################################################################################
  157. ##########################################################################################
  158. class Enumerate(dict):
  159. """C enum emulation (original by Scott David Daniels)"""
  160. def __init__(self, names):
  161. for number, name in enumerate(names.split()):
  162. setattr(self, name, number)
  163. self[number] = name
  164. class SharedData(object):
  165. """Data used in all three main classes"""
  166. #Possible kinds of symbol table entries
  167. KINDS = Enumerate("NO_KIND WORKING_REGISTER GLOBAL_VAR FUNCTION PARAMETER LOCAL_VAR CONSTANT")
  168. #Supported types of functions and variables
  169. TYPES = Enumerate("NO_TYPE INT UNSIGNED")
  170. #bit size of variables
  171. TYPE_BIT_SIZE = 16
  172. #min/max values of constants
  173. MIN_INT = -2 ** (TYPE_BIT_SIZE - 1)
  174. MAX_INT = 2 ** (TYPE_BIT_SIZE - 1) - 1
  175. MAX_UNSIGNED = 2 ** TYPE_BIT_SIZE - 1
  176. #available working registers (the last one is the register for function's return value!)
  177. REGISTERS = "%0 %1 %2 %3 %4 %5 %6 %7 %8 %9 %10 %11 %12 %13".split()
  178. #register for function's return value
  179. FUNCTION_REGISTER = len(REGISTERS) - 1
  180. #the index of last working register
  181. LAST_WORKING_REGISTER = len(REGISTERS) - 2
  182. #list of relational operators
  183. RELATIONAL_OPERATORS = "< > <= >= == !=".split()
  184. def __init__(self):
  185. #index of the currently parsed function
  186. self.functon_index = 0
  187. #name of the currently parsed function
  188. self.functon_name = 0
  189. #number of parameters of the currently parsed function
  190. self.function_params = 0
  191. #number of local variables of the currently parsed function
  192. self.function_vars = 0
  193. ##########################################################################################
  194. ##########################################################################################
  195. class ExceptionSharedData(object):
  196. """Class for exception handling data"""
  197. def __init__(self):
  198. #position in currently parsed text
  199. self.location = 0
  200. #currently parsed text
  201. self.text = ""
  202. def setpos(self, location, text):
  203. """Helper function for setting curently parsed text and position"""
  204. self.location = location
  205. self.text = text
  206. exshared = ExceptionSharedData()
  207. class SemanticException(Exception):
  208. """Exception for semantic errors found during parsing, similar to ParseException.
  209. Introduced because ParseException is used internally in pyparsing and custom
  210. messages got lost and replaced by pyparsing's generic errors.
  211. """
  212. def __init__(self, message, print_location=True):
  213. super(SemanticException,self).__init__()
  214. self._message = message
  215. self.location = exshared.location
  216. self.print_location = print_location
  217. if exshared.location != None:
  218. self.line = lineno(exshared.location, exshared.text)
  219. self.col = col(exshared.location, exshared.text)
  220. self.text = line(exshared.location, exshared.text)
  221. else:
  222. self.line = self.col = self.text = None
  223. def _get_message(self):
  224. return self._message
  225. def _set_message(self, message):
  226. self._message = message
  227. message = property(_get_message, _set_message)
  228. def __str__(self):
  229. """String representation of the semantic error"""
  230. msg = "Error"
  231. if self.print_location and (self.line != None):
  232. msg += " at line %d, col %d" % (self.line, self.col)
  233. msg += ": %s" % self.message
  234. if self.print_location and (self.line != None):
  235. msg += "\n%s" % self.text
  236. return msg
  237. ##########################################################################################
  238. ##########################################################################################
  239. class SymbolTableEntry(object):
  240. """Class which represents one symbol table entry."""
  241. def __init__(self, sname = "", skind = 0, stype = 0, sattr = None, sattr_name = "None"):
  242. """Initialization of symbol table entry.
  243. sname - symbol name
  244. skind - symbol kind
  245. stype - symbol type
  246. sattr - symbol attribute
  247. sattr_name - symbol attribute name (used only for table display)
  248. """
  249. self.name = sname
  250. self.kind = skind
  251. self.type = stype
  252. self.attribute = sattr
  253. self.attribute_name = sattr_name
  254. self.param_types = []
  255. def set_attribute(self, name, value):
  256. """Sets attribute's name and value"""
  257. self.attribute_name = name
  258. self.attribute = value
  259. def attribute_str(self):
  260. """Returns attribute string (used only for table display)"""
  261. return "{0}={1}".format(self.attribute_name, self.attribute) if self.attribute != None else "None"
  262. class SymbolTable(object):
  263. """Class for symbol table of microC program"""
  264. def __init__(self, shared):
  265. """Initialization of the symbol table"""
  266. self.table = []
  267. self.lable_len = 0
  268. #put working registers in the symbol table
  269. for reg in range(SharedData.FUNCTION_REGISTER+1):
  270. self.insert_symbol(SharedData.REGISTERS[reg], SharedData.KINDS.WORKING_REGISTER, SharedData.TYPES.NO_TYPE)
  271. #shared data
  272. self.shared = shared
  273. def error(self, text=""):
  274. """Symbol table error exception. It should happen only if index is out of range while accessing symbol table.
  275. This exeption is not handled by the compiler, so as to allow traceback printing
  276. """
  277. if text == "":
  278. raise Exception("Symbol table index out of range")
  279. else:
  280. raise Exception("Symbol table error: %s" % text)
  281. def display(self):
  282. """Displays the symbol table content"""
  283. #Finding the maximum length for each column
  284. sym_name = "Symbol name"
  285. sym_len = max(max(len(i.name) for i in self.table),len(sym_name))
  286. kind_name = "Kind"
  287. kind_len = max(max(len(SharedData.KINDS[i.kind]) for i in self.table),len(kind_name))
  288. type_name = "Type"
  289. type_len = max(max(len(SharedData.TYPES[i.type]) for i in self.table),len(type_name))
  290. attr_name = "Attribute"
  291. attr_len = max(max(len(i.attribute_str()) for i in self.table),len(attr_name))
  292. #print table header
  293. print("{0:3s} | {1:^{2}s} | {3:^{4}s} | {5:^{6}s} | {7:^{8}} | {9:s}".format(" No", sym_name, sym_len, kind_name, kind_len, type_name, type_len, attr_name, attr_len, "Parameters"))
  294. print("-----------------------------" + "-" * (sym_len + kind_len + type_len + attr_len))
  295. #print symbol table
  296. for i,sym in enumerate(self.table):
  297. parameters = ""
  298. for p in sym.param_types:
  299. if parameters == "":
  300. parameters = "{0}".format(SharedData.TYPES[p])
  301. else:
  302. parameters += ", {0}".format(SharedData.TYPES[p])
  303. print("{0:3d} | {1:^{2}s} | {3:^{4}s} | {5:^{6}s} | {7:^{8}} | ({9})".format(i, sym.name, sym_len, SharedData.KINDS[sym.kind], kind_len, SharedData.TYPES[sym.type], type_len, sym.attribute_str(), attr_len, parameters))
  304. def insert_symbol(self, sname, skind, stype):
  305. """Inserts new symbol at the end of the symbol table.
  306. Returns symbol index
  307. sname - symbol name
  308. skind - symbol kind
  309. stype - symbol type
  310. """
  311. self.table.append(SymbolTableEntry(sname, skind, stype))
  312. self.table_len = len(self.table)
  313. return self.table_len-1
  314. def clear_symbols(self, index):
  315. """Clears all symbols begining with the index to the end of table"""
  316. try:
  317. del self.table[index:]
  318. except Exception:
  319. self.error()
  320. self.table_len = len(self.table)
  321. def lookup_symbol(self, sname, skind=list(SharedData.KINDS.keys()), stype=list(SharedData.TYPES.keys())):
  322. """Searches for symbol, from the end to the begining.
  323. Returns symbol index or None
  324. sname - symbol name
  325. skind - symbol kind (one kind, list of kinds, or None) deafult: any kind
  326. stype - symbol type (or None) default: any type
  327. """
  328. skind = skind if isinstance(skind, list) else [skind]
  329. stype = stype if isinstance(stype, list) else [stype]
  330. for i, sym in [[x, self.table[x]] for x in range(len(self.table) - 1, SharedData.LAST_WORKING_REGISTER, -1)]:
  331. if (sym.name == sname) and (sym.kind in skind) and (sym.type in stype):
  332. return i
  333. return None
  334. def insert_id(self, sname, skind, skinds, stype):
  335. """Inserts a new identifier at the end of the symbol table, if possible.
  336. Returns symbol index, or raises an exception if the symbol alredy exists
  337. sname - symbol name
  338. skind - symbol kind
  339. skinds - symbol kinds to check for
  340. stype - symbol type
  341. """
  342. index = self.lookup_symbol(sname, skinds)
  343. if index == None:
  344. index = self.insert_symbol(sname, skind, stype)
  345. return index
  346. else:
  347. raise SemanticException("Redefinition of '%s'" % sname)
  348. def insert_global_var(self, vname, vtype):
  349. "Inserts a new global variable"
  350. return self.insert_id(vname, SharedData.KINDS.GLOBAL_VAR, [SharedData.KINDS.GLOBAL_VAR, SharedData.KINDS.FUNCTION], vtype)
  351. def insert_local_var(self, vname, vtype, position):
  352. "Inserts a new local variable"
  353. index = self.insert_id(vname, SharedData.KINDS.LOCAL_VAR, [SharedData.KINDS.LOCAL_VAR, SharedData.KINDS.PARAMETER], vtype)
  354. self.table[index].attribute = position
  355. def insert_parameter(self, pname, ptype):
  356. "Inserts a new parameter"
  357. index = self.insert_id(pname, SharedData.KINDS.PARAMETER, SharedData.KINDS.PARAMETER, ptype)
  358. #set parameter's attribute to it's ordinal number
  359. self.table[index].set_attribute("Index", self.shared.function_params)
  360. #set parameter's type in param_types list of a function
  361. self.table[self.shared.function_index].param_types.append(ptype)
  362. return index
  363. def insert_function(self, fname, ftype):
  364. "Inserts a new function"
  365. index = self.insert_id(fname, SharedData.KINDS.FUNCTION, [SharedData.KINDS.GLOBAL_VAR, SharedData.KINDS.FUNCTION], ftype)
  366. self.table[index].set_attribute("Params",0)
  367. return index
  368. def insert_constant(self, cname, ctype):
  369. """Inserts a constant (or returns index if the constant already exists)
  370. Additionally, checks for range.
  371. """
  372. index = self.lookup_symbol(cname, stype=ctype)
  373. if index == None:
  374. num = int(cname)
  375. if ctype == SharedData.TYPES.INT:
  376. if (num < SharedData.MIN_INT) or (num > SharedData.MAX_INT):
  377. raise SemanticException("Integer constant '%s' out of range" % cname)
  378. elif ctype == SharedData.TYPES.UNSIGNED:
  379. if (num < 0) or (num > SharedData.MAX_UNSIGNED):
  380. raise SemanticException("Unsigned constant '%s' out of range" % cname)
  381. index = self.insert_symbol(cname, SharedData.KINDS.CONSTANT, ctype)
  382. return index
  383. def same_types(self, index1, index2):
  384. """Returns True if both symbol table elements are of the same type"""
  385. try:
  386. same = self.table[index1].type == self.table[index2].type != SharedData.TYPES.NO_TYPE
  387. except Exception:
  388. self.error()
  389. return same
  390. def same_type_as_argument(self, index, function_index, argument_number):
  391. """Returns True if index and function's argument are of the same type
  392. index - index in symbol table
  393. function_index - function's index in symbol table
  394. argument_number - # of function's argument
  395. """
  396. try:
  397. same = self.table[function_index].param_types[argument_number] == self.table[index].type
  398. except Exception:
  399. self.error()
  400. return same
  401. def get_attribute(self, index):
  402. try:
  403. return self.table[index].attribute
  404. except Exception:
  405. self.error()
  406. def set_attribute(self, index, value):
  407. try:
  408. self.table[index].attribute = value
  409. except Exception:
  410. self.error()
  411. def get_name(self, index):
  412. try:
  413. return self.table[index].name
  414. except Exception:
  415. self.error()
  416. def get_kind(self, index):
  417. try:
  418. return self.table[index].kind
  419. except Exception:
  420. self.error()
  421. def get_type(self, index):
  422. try:
  423. return self.table[index].type
  424. except Exception:
  425. self.error()
  426. def set_type(self, index, stype):
  427. try:
  428. self.table[index].type = stype
  429. except Exception:
  430. self.error()
  431. ##########################################################################################
  432. ##########################################################################################
  433. class CodeGenerator(object):
  434. """Class for code generation methods."""
  435. #dictionary of relational operators
  436. RELATIONAL_DICT = {op:i for i, op in enumerate(SharedData.RELATIONAL_OPERATORS)}
  437. #conditional jumps for relational operators
  438. CONDITIONAL_JUMPS = ["JLTS", "JGTS", "JLES", "JGES", "JEQ ", "JNE ",
  439. "JLTU", "JGTU", "JLEU", "JGEU", "JEQ ", "JNE "]
  440. #opposite conditional jumps for relational operators
  441. OPPOSITE_JUMPS = ["JGES", "JLES", "JGTS", "JLTS", "JNE ", "JEQ ",
  442. "JGEU", "JLEU", "JGTU", "JLTU", "JNE ", "JEQ "]
  443. #supported operations
  444. OPERATIONS = {"+" : "ADD", "-" : "SUB", "*" : "MUL", "/" : "DIV"}
  445. #suffixes for signed and unsigned operations (if no type is specified, unsigned will be assumed)
  446. OPSIGNS = {SharedData.TYPES.NO_TYPE : "U", SharedData.TYPES.INT : "S", SharedData.TYPES.UNSIGNED : "U"}
  447. #text at start of data segment
  448. DATA_START_TEXT = "#DATA"
  449. #text at start of code segment
  450. CODE_START_TEXT = "#CODE"
  451. def __init__(self, shared, symtab):
  452. #generated code
  453. self.code = ""
  454. #prefix for internal labels
  455. self.internal = "@"
  456. #suffix for label definition
  457. self.definition = ":"
  458. #list of free working registers
  459. self.free_registers = list(range(SharedData.FUNCTION_REGISTER, -1, -1))
  460. #list of used working registers
  461. self.used_registers = []
  462. #list of used registers needed when function call is inside of a function call
  463. self.used_registers_stack = []
  464. #shared data
  465. self.shared = shared
  466. #symbol table
  467. self.symtab = symtab
  468. def error(self, text):
  469. """Compiler error exception. It should happen only if something is wrong with compiler.
  470. This exeption is not handled by the compiler, so as to allow traceback printing
  471. """
  472. raise Exception("Compiler error: %s" % text)
  473. def take_register(self, rtype = SharedData.TYPES.NO_TYPE):
  474. """Reserves one working register and sets its type"""
  475. if len(self.free_registers) == 0:
  476. self.error("no more free registers")
  477. reg = self.free_registers.pop()
  478. self.used_registers.append(reg)
  479. self.symtab.set_type(reg, rtype)
  480. return reg
  481. def take_function_register(self, rtype = SharedData.TYPES.NO_TYPE):
  482. """Reserves register for function return value and sets its type"""
  483. reg = SharedData.FUNCTION_REGISTER
  484. if reg not in self.free_registers:
  485. self.error("function register already taken")
  486. self.free_registers.remove(reg)
  487. self.used_registers.append(reg)
  488. self.symtab.set_type(reg, rtype)
  489. return reg
  490. def free_register(self, reg):
  491. """Releases working register"""
  492. if reg not in self.used_registers:
  493. self.error("register %s is not taken" % self.REGISTERS[reg])
  494. self.used_registers.remove(reg)
  495. self.free_registers.append(reg)
  496. self.free_registers.sort(reverse = True)
  497. def free_if_register(self, index):
  498. """If index is a working register, free it, otherwise just return (helper function)"""
  499. if (index < 0) or (index > SharedData.FUNCTION_REGISTER):
  500. return
  501. else:
  502. self.free_register(index)
  503. def label(self, name, internal=False, definition=False):
  504. """Generates label name (helper function)
  505. name - label name
  506. internal - boolean value, adds "@" prefix to label
  507. definition - boolean value, adds ":" suffix to label
  508. """
  509. return "{0}{1}{2}".format(self.internal if internal else "", name, self.definition if definition else "")
  510. def symbol(self, index):
  511. """Generates symbol name from index"""
  512. #if index is actually a string, just return it
  513. if isinstance(index, str):
  514. return index
  515. elif (index < 0) or (index >= self.symtab.table_len):
  516. self.error("symbol table index out of range")
  517. sym = self.symtab.table[index]
  518. #local variables are located at negative offset from frame pointer register
  519. if sym.kind == SharedData.KINDS.LOCAL_VAR:
  520. return "-{0}(1:%14)".format(sym.attribute * 4 + 4)
  521. #parameters are located at positive offset from frame pointer register
  522. elif sym.kind == SharedData.KINDS.PARAMETER:
  523. return "{0}(1:%14)".format(8 + sym.attribute * 4)
  524. elif sym.kind == SharedData.KINDS.CONSTANT:
  525. return "${0}".format(sym.name)
  526. else:
  527. return "{0}".format(sym.name)
  528. def save_used_registers(self):
  529. """Pushes all used working registers before function call"""
  530. used = self.used_registers[:]
  531. del self.used_registers[:]
  532. self.used_registers_stack.append(used[:])
  533. used.sort()
  534. for reg in used:
  535. self.newline_text("PUSH\t%s" % SharedData.REGISTERS[reg], True)
  536. self.free_registers.extend(used)
  537. self.free_registers.sort(reverse = True)
  538. def restore_used_registers(self):
  539. """Pops all used working registers after function call"""
  540. used = self.used_registers_stack.pop()
  541. self.used_registers = used[:]
  542. used.sort(reverse = True)
  543. for reg in used:
  544. self.newline_text("POP \t%s" % SharedData.REGISTERS[reg], True)
  545. self.free_registers.remove(reg)
  546. def text(self, text):
  547. """Inserts text into generated code"""
  548. self.code += text
  549. def prepare_data_segment(self):
  550. """Inserts text at the start of data segment"""
  551. self.text(self.DATA_START_TEXT)
  552. def prepare_code_segment(self):
  553. """Inserts text at the start of code segment"""
  554. self.newline_text(self.CODE_START_TEXT)
  555. def newline(self, indent=False):
  556. """Inserts a newline, optionally with indentation."""
  557. self.text("\n")
  558. if indent:
  559. self.text("\t\t\t")
  560. def newline_text(self, text, indent = False):
  561. """Inserts a newline and text, optionally with indentation (helper function)"""
  562. self.newline(indent)
  563. self.text(text)
  564. def newline_label(self, name, internal=False, definition=False):
  565. """Inserts a newline and a label (helper function)
  566. name - label name
  567. internal - boolean value, adds "@" prefix to label
  568. definition - boolean value, adds ":" suffix to label
  569. """
  570. self.newline_text(self.label("{0}{1}{2}".format("@" if internal else "", name, ":" if definition else "")))
  571. def global_var(self, name):
  572. """Inserts a new static (global) variable definition"""
  573. self.newline_label(name, False, True)
  574. self.newline_text("WORD\t1", True)
  575. def arithmetic_mnemonic(self, op_name, op_type):
  576. """Generates an arithmetic instruction mnemonic"""
  577. return self.OPERATIONS[op_name] + self.OPSIGNS[op_type]
  578. def arithmetic(self, operation, operand1, operand2, operand3 = None):
  579. """Generates an arithmetic instruction
  580. operation - one of supporetd operations
  581. operandX - index in symbol table or text representation of operand
  582. First two operands are input, third one is output
  583. """
  584. if isinstance(operand1, int):
  585. output_type = self.symtab.get_type(operand1)
  586. self.free_if_register(operand1)
  587. else:
  588. output_type = None
  589. if isinstance(operand2, int):
  590. output_type = self.symtab.get_type(operand2) if output_type == None else output_type
  591. self.free_if_register(operand2)
  592. else:
  593. output_type = SharedData.TYPES.NO_TYPE if output_type == None else output_type
  594. #if operand3 is not defined, reserve one free register for it
  595. output = self.take_register(output_type) if operand3 == None else operand3
  596. mnemonic = self.arithmetic_mnemonic(operation, output_type)
  597. self.newline_text("{0}\t{1},{2},{3}".format(mnemonic, self.symbol(operand1), self.symbol(operand2), self.symbol(output)), True)
  598. return output
  599. def relop_code(self, relop, operands_type):
  600. """Returns code for relational operator
  601. relop - relational operator
  602. operands_type - int or unsigned
  603. """
  604. code = self.RELATIONAL_DICT[relop]
  605. offset = 0 if operands_type == SharedData.TYPES.INT else len(SharedData.RELATIONAL_OPERATORS)
  606. return code + offset
  607. def jump(self, relcode, opposite, label):
  608. """Generates a jump instruction
  609. relcode - relational operator code
  610. opposite - generate normal or opposite jump
  611. label - jump label
  612. """
  613. jump = self.OPPOSITE_JUMPS[relcode] if opposite else self.CONDITIONAL_JUMPS[relcode]
  614. self.newline_text("{0}\t{1}".format(jump, label), True)
  615. def unconditional_jump(self, label):
  616. """Generates an unconditional jump instruction
  617. label - jump label
  618. """
  619. self.newline_text("JMP \t{0}".format(label), True)
  620. def move(self,operand1, operand2):
  621. """Generates a move instruction
  622. If the output operand (opernad2) is a working register, sets it's type
  623. operandX - index in symbol table or text representation of operand
  624. """
  625. if isinstance(operand1, int):
  626. output_type = self.symtab.get_type(operand1)
  627. self.free_if_register(operand1)
  628. else:
  629. output_type = SharedData.TYPES.NO_TYPE
  630. self.newline_text("MOV \t{0},{1}".format(self.symbol(operand1), self.symbol(operand2)), True)
  631. if isinstance(operand2, int):
  632. if self.symtab.get_kind(operand2) == SharedData.KINDS.WORKING_REGISTER:
  633. self.symtab.set_type(operand2, output_type)
  634. def push(self, operand):
  635. """Generates a push operation"""
  636. self.newline_text("PUSH\t%s" % self.symbol(operand), True)
  637. def pop(self, operand):
  638. """Generates a pop instruction"""
  639. self.newline_text("POP \t%s" % self.symbol(operand), True)
  640. def compare(self, operand1, operand2):
  641. """Generates a compare instruction
  642. operandX - index in symbol table
  643. """
  644. typ = self.symtab.get_type(operand1)
  645. self.free_if_register(operand1)
  646. self.free_if_register(operand2)
  647. self.newline_text("CMP{0}\t{1},{2}".format(self.OPSIGNS[typ], self.symbol(operand1), self.symbol(operand2)), True)
  648. def function_begin(self):
  649. """Inserts function name label and function frame initialization"""
  650. self.newline_label(self.shared.function_name, False, True)
  651. self.push("%14")
  652. self.move("%15", "%14")
  653. def function_body(self):
  654. """Inserts a local variable initialization and body label"""
  655. if self.shared.function_vars > 0:
  656. const = self.symtab.insert_constant("0{}".format(self.shared.function_vars * 4), SharedData.TYPES.UNSIGNED)
  657. self.arithmetic("-", "%15", const, "%15")
  658. self.newline_label(self.shared.function_name + "_body", True, True)
  659. def function_end(self):
  660. """Inserts an exit label and function return instructions"""
  661. self.newline_label(self.shared.function_name + "_exit", True, True)
  662. self.move("%14", "%15")
  663. self.pop("%14")
  664. self.newline_text("RET", True)
  665. def function_call(self, function, arguments):
  666. """Generates code for a function call
  667. function - function index in symbol table
  668. arguments - list of arguments (indexes in symbol table)
  669. """
  670. #push each argument to stack
  671. for arg in arguments:
  672. self.push(self.symbol(arg))
  673. self.free_if_register(arg)
  674. self.newline_text("CALL\t"+self.symtab.get_name(function), True)
  675. args = self.symtab.get_attribute(function)
  676. #generates stack cleanup if function has arguments
  677. if args > 0:
  678. args_space = self.symtab.insert_constant("{0}".format(args * 4), SharedData.TYPES.UNSIGNED)
  679. self.arithmetic("+", "%15", args_space, "%15")
  680. ##########################################################################################
  681. ##########################################################################################
  682. class MicroC(object):
  683. """Class for microC parser/compiler"""
  684. def __init__(self):
  685. #Definitions of terminal symbols for microC programming language
  686. self.tId = Word(alphas+"_",alphanums+"_")
  687. self.tInteger = Word(nums).setParseAction(lambda x : [x[0], SharedData.TYPES.INT])
  688. self.tUnsigned = Regex(r"[0-9]+[uU]").setParseAction(lambda x : [x[0][:-1], SharedData.TYPES.UNSIGNED])
  689. self.tConstant = (self.tUnsigned | self.tInteger).setParseAction(self.constant_action)
  690. self.tType = Keyword("int").setParseAction(lambda x : SharedData.TYPES.INT) | \
  691. Keyword("unsigned").setParseAction(lambda x : SharedData.TYPES.UNSIGNED)
  692. self.tRelOp = oneOf(SharedData.RELATIONAL_OPERATORS)
  693. self.tMulOp = oneOf("* /")
  694. self.tAddOp = oneOf("+ -")
  695. #Definitions of rules for global variables
  696. self.rGlobalVariable = (self.tType("type") + self.tId("name") +
  697. FollowedBy(";")).setParseAction(self.global_variable_action)
  698. self.rGlobalVariableList = ZeroOrMore(self.rGlobalVariable + Suppress(";"))
  699. #Definitions of rules for numeric expressions
  700. self.rExp = Forward()
  701. self.rMulExp = Forward()
  702. self.rNumExp = Forward()
  703. self.rArguments = delimitedList(self.rNumExp("exp").setParseAction(self.argument_action))
  704. self.rFunctionCall = ((self.tId("name") + FollowedBy("(")).setParseAction(self.function_call_prepare_action) +
  705. Suppress("(") + Optional(self.rArguments)("args") + Suppress(")")).setParseAction(self.function_call_action)
  706. self.rExp << (self.rFunctionCall |
  707. self.tConstant |
  708. self.tId("name").setParseAction(self.lookup_id_action) |
  709. Group(Suppress("(") + self.rNumExp + Suppress(")")) |
  710. Group("+" + self.rExp) |
  711. Group("-" + self.rExp)).setParseAction(lambda x : x[0])
  712. self.rMulExp << ((self.rExp + ZeroOrMore(self.tMulOp + self.rExp))).setParseAction(self.mulexp_action)
  713. self.rNumExp << (self.rMulExp + ZeroOrMore(self.tAddOp + self.rMulExp)).setParseAction(self.numexp_action)
  714. #Definitions of rules for logical expressions (these are without parenthesis support)
  715. self.rAndExp = Forward()
  716. self.rLogExp = Forward()
  717. self.rRelExp = (self.rNumExp + self.tRelOp + self.rNumExp).setParseAction(self.relexp_action)
  718. self.rAndExp << (self.rRelExp("exp") + ZeroOrMore(Literal("&&").setParseAction(self.andexp_action) +
  719. self.rRelExp("exp")).setParseAction(lambda x : self.relexp_code))
  720. self.rLogExp << (self.rAndExp("exp") + ZeroOrMore(Literal("||").setParseAction(self.logexp_action) +
  721. self.rAndExp("exp")).setParseAction(lambda x : self.andexp_code))
  722. #Definitions of rules for statements
  723. self.rStatement = Forward()
  724. self.rStatementList = Forward()
  725. self.rReturnStatement = (Keyword("return") + self.rNumExp("exp") +
  726. Suppress(";")).setParseAction(self.return_action)
  727. self.rAssignmentStatement = (self.tId("var") + Suppress("=") + self.rNumExp("exp") +
  728. Suppress(";")).setParseAction(self.assignment_action)
  729. self.rFunctionCallStatement = self.rFunctionCall + Suppress(";")
  730. self.rIfStatement = ( (Keyword("if") + FollowedBy("(")).setParseAction(self.if_begin_action) +
  731. (Suppress("(") + self.rLogExp + Suppress(")")).setParseAction(self.if_body_action) +
  732. (self.rStatement + Empty()).setParseAction(self.if_else_action) +
  733. Optional(Keyword("else") + self.rStatement)).setParseAction(self.if_end_action)
  734. self.rWhileStatement = ( (Keyword("while") + FollowedBy("(")).setParseAction(self.while_begin_action) +
  735. (Suppress("(") + self.rLogExp + Suppress(")")).setParseAction(self.while_body_action) +
  736. self.rStatement).setParseAction(self.while_end_action)
  737. self.rCompoundStatement = Group(Suppress("{") + self.rStatementList + Suppress("}"))
  738. self.rStatement << (self.rReturnStatement | self.rIfStatement | self.rWhileStatement |
  739. self.rFunctionCallStatement | self.rAssignmentStatement | self.rCompoundStatement)
  740. self.rStatementList << ZeroOrMore(self.rStatement)
  741. self.rLocalVariable = (self.tType("type") + self.tId("name") + FollowedBy(";")).setParseAction(self.local_variable_action)
  742. self.rLocalVariableList = ZeroOrMore(self.rLocalVariable + Suppress(";"))
  743. self.rFunctionBody = Suppress("{") + Optional(self.rLocalVariableList).setParseAction(self.function_body_action) + \
  744. self.rStatementList + Suppress("}")
  745. self.rParameter = (self.tType("type") + self.tId("name")).setParseAction(self.parameter_action)
  746. self.rParameterList = delimitedList(self.rParameter)
  747. self.rFunction = ( (self.tType("type") + self.tId("name")).setParseAction(self.function_begin_action) +
  748. Group(Suppress("(") + Optional(self.rParameterList)("params") + Suppress(")") +
  749. self.rFunctionBody)).setParseAction(self.function_end_action)
  750. self.rFunctionList = OneOrMore(self.rFunction)
  751. self.rProgram = (Empty().setParseAction(self.data_begin_action) + self.rGlobalVariableList +
  752. Empty().setParseAction(self.code_begin_action) + self.rFunctionList).setParseAction(self.program_end_action)
  753. #shared data
  754. self.shared = SharedData()
  755. #symbol table
  756. self.symtab = SymbolTable(self.shared)
  757. #code generator
  758. self.codegen = CodeGenerator(self.shared, self.symtab)
  759. #index of the current function call
  760. self.function_call_index = -1
  761. #stack for the nested function calls
  762. self.function_call_stack = []
  763. #arguments of the current function call
  764. self.function_arguments = []
  765. #stack for arguments of the nested function calls
  766. self.function_arguments_stack = []
  767. #number of arguments for the curent function call
  768. self.function_arguments_number = -1
  769. #stack for the number of arguments for the nested function calls
  770. self.function_arguments_number_stack = []
  771. #last relational expression
  772. self.relexp_code = None
  773. #last and expression
  774. self.andexp_code = None
  775. #label number for "false" internal labels
  776. self.false_label_number = -1
  777. #label number for all other internal labels
  778. self.label_number = None
  779. #label stack for nested statements
  780. self.label_stack = []
  781. def warning(self, message, print_location=True):
  782. """Displays warning message. Uses exshared for current location of parsing"""
  783. msg = "Warning"
  784. if print_location and (exshared.location != None):
  785. wline = lineno(exshared.location, exshared.text)
  786. wcol = col(exshared.location, exshared.text)
  787. wtext = line(exshared.location, exshared.text)
  788. msg += " at line %d, col %d" % (wline, wcol)
  789. msg += ": %s" % message
  790. if print_location and (exshared.location != None):
  791. msg += "\n%s" % wtext
  792. print(msg)
  793. def data_begin_action(self):
  794. """Inserts text at start of data segment"""
  795. self.codegen.prepare_data_segment()
  796. def code_begin_action(self):
  797. """Inserts text at start of code segment"""
  798. self.codegen.prepare_code_segment()
  799. def global_variable_action(self, text, loc, var):
  800. """Code executed after recognising a global variable"""
  801. exshared.setpos(loc, text)
  802. if DEBUG > 0:
  803. print("GLOBAL_VAR:",var)
  804. if DEBUG == 2: self.symtab.display()
  805. if DEBUG > 2: return
  806. index = self.symtab.insert_global_var(var.name, var.type)
  807. self.codegen.global_var(var.name)
  808. return index
  809. def local_variable_action(self, text, loc, var):
  810. """Code executed after recognising a local variable"""
  811. exshared.setpos(loc, text)
  812. if DEBUG > 0:
  813. print("LOCAL_VAR:",var, var.name, var.type)
  814. if DEBUG == 2: self.symtab.display()
  815. if DEBUG > 2: return
  816. index = self.symtab.insert_local_var(var.name, var.type, self.shared.function_vars)
  817. self.shared.function_vars += 1
  818. return index
  819. def parameter_action(self, text, loc, par):
  820. """Code executed after recognising a parameter"""
  821. exshared.setpos(loc, text)
  822. if DEBUG > 0:
  823. print("PARAM:",par)
  824. if DEBUG == 2: self.symtab.display()
  825. if DEBUG > 2: return
  826. index = self.symtab.insert_parameter(par.name, par.type)
  827. self.shared.function_params += 1
  828. return index
  829. def constant_action(self, text, loc, const):
  830. """Code executed after recognising a constant"""
  831. exshared.setpos(loc, text)
  832. if DEBUG > 0:
  833. print("CONST:",const)
  834. if DEBUG == 2: self.symtab.display()
  835. if DEBUG > 2: return
  836. return self.symtab.insert_constant(const[0], const[1])
  837. def function_begin_action(self, text, loc, fun):
  838. """Code executed after recognising a function definition (type and function name)"""
  839. exshared.setpos(loc, text)
  840. if DEBUG > 0:
  841. print("FUN_BEGIN:",fun)
  842. if DEBUG == 2: self.symtab.display()
  843. if DEBUG > 2: return
  844. self.shared.function_index = self.symtab.insert_function(fun.name, fun.type)
  845. self.shared.function_name = fun.name
  846. self.shared.function_params = 0
  847. self.shared.function_vars = 0
  848. self.codegen.function_begin();
  849. def function_body_action(self, text, loc, fun):
  850. """Code executed after recognising the beginning of function's body"""
  851. exshared.setpos(loc, text)
  852. if DEBUG > 0:
  853. print("FUN_BODY:",fun)
  854. if DEBUG == 2: self.symtab.display()
  855. if DEBUG > 2: return
  856. self.codegen.function_body()
  857. def function_end_action(self, text, loc, fun):
  858. """Code executed at the end of function definition"""
  859. if DEBUG > 0:
  860. print("FUN_END:",fun)
  861. if DEBUG == 2: self.symtab.display()
  862. if DEBUG > 2: return
  863. #set function's attribute to number of function parameters
  864. self.symtab.set_attribute(self.shared.function_index, self.shared.function_params)
  865. #clear local function symbols (but leave function name)
  866. self.symtab.clear_symbols(self.shared.function_index + 1)
  867. self.codegen.function_end()
  868. def return_action(self, text, loc, ret):
  869. """Code executed after recognising a return statement"""
  870. exshared.setpos(loc, text)
  871. if DEBUG > 0:
  872. print("RETURN:",ret)
  873. if DEBUG == 2: self.symtab.display()
  874. if DEBUG > 2: return
  875. if not self.symtab.same_types(self.shared.function_index, ret.exp[0]):
  876. raise SemanticException("Incompatible type in return")
  877. #set register for function's return value to expression value
  878. reg = self.codegen.take_function_register()
  879. self.codegen.move(ret.exp[0], reg)
  880. #after return statement, register for function's return value is available again
  881. self.codegen.free_register(reg)
  882. #jump to function's exit
  883. self.codegen.unconditional_jump(self.codegen.label(self.shared.function_name+"_exit", True))
  884. def lookup_id_action(self, text, loc, var):
  885. """Code executed after recognising an identificator in expression"""
  886. exshared.setpos(loc, text)
  887. if DEBUG > 0:
  888. print("EXP_VAR:",var)
  889. if DEBUG == 2: self.symtab.display()
  890. if DEBUG > 2: return
  891. var_index = self.symtab.lookup_symbol(var.name, [SharedData.KINDS.GLOBAL_VAR, SharedData.KINDS.PARAMETER, SharedData.KINDS.LOCAL_VAR])
  892. if var_index == None:
  893. raise SemanticException("'%s' undefined" % var.name)
  894. return var_index
  895. def assignment_action(self, text, loc, assign):
  896. """Code executed after recognising an assignment statement"""
  897. exshared.setpos(loc, text)
  898. if DEBUG > 0:
  899. print("ASSIGN:",assign)
  900. if DEBUG == 2: self.symtab.display()
  901. if DEBUG > 2: return
  902. var_index = self.symtab.lookup_symbol(assign.var, [SharedData.KINDS.GLOBAL_VAR, SharedData.KINDS.PARAMETER, SharedData.KINDS.LOCAL_VAR])
  903. if var_index == None:
  904. raise SemanticException("Undefined lvalue '%s' in assignment" % assign.var)
  905. if not self.symtab.same_types(var_index, assign.exp[0]):
  906. raise SemanticException("Incompatible types in assignment")
  907. self.codegen.move(assign.exp[0], var_index)
  908. def mulexp_action(self, text, loc, mul):
  909. """Code executed after recognising a mulexp expression (something *|/ something)"""
  910. exshared.setpos(loc, text)
  911. if DEBUG > 0:
  912. print("MUL_EXP:",mul)
  913. if DEBUG == 2: self.symtab.display()
  914. if DEBUG > 2: return
  915. #iterate through all multiplications/divisions
  916. m = list(mul)
  917. while len(m) > 1:
  918. if not self.symtab.same_types(m[0], m[2]):
  919. raise SemanticException("Invalid opernads to binary '%s'" % m[1])
  920. reg = self.codegen.arithmetic(m[1], m[0], m[2])
  921. #replace first calculation with it's result
  922. m[0:3] = [reg]
  923. return m[0]
  924. def numexp_action(self, text, loc, num):
  925. """Code executed after recognising a numexp expression (something +|- something)"""
  926. exshared.setpos(loc, text)
  927. if DEBUG > 0:
  928. print("NUM_EXP:",num)
  929. if DEBUG == 2: self.symtab.display()
  930. if DEBUG > 2: return
  931. #iterate through all additions/substractions
  932. n = list(num)
  933. while len(n) > 1:
  934. if not self.symtab.same_types(n[0], n[2]):
  935. raise SemanticException("Invalid opernads to binary '%s'" % n[1])
  936. reg = self.codegen.arithmetic(n[1], n[0], n[2])
  937. #replace first calculation with it's result
  938. n[0:3] = [reg]
  939. return n[0]
  940. def function_call_prepare_action(self, text, loc, fun):
  941. """Code executed after recognising a function call (type and function name)"""
  942. exshared.setpos(loc, text)
  943. if DEBUG > 0:
  944. print("FUN_PREP:",fun)
  945. if DEBUG == 2: self.symtab.display()
  946. if DEBUG > 2: return
  947. index = self.symtab.lookup_symbol(fun.name, SharedData.KINDS.FUNCTION)
  948. if index == None:
  949. raise SemanticException("'%s' is not a function" % fun.name)
  950. #save any previous function call data (for nested function calls)
  951. self.function_call_stack.append(self.function_call_index)
  952. self.function_call_index = index
  953. self.function_arguments_stack.append(self.function_arguments[:])
  954. del self.function_arguments[:]
  955. self.codegen.save_used_registers()
  956. def argument_action(self, text, loc, arg):
  957. """Code executed after recognising each of function's arguments"""
  958. exshared.setpos(loc, text)
  959. if DEBUG > 0:
  960. print("ARGUMENT:",arg.exp)
  961. if DEBUG == 2: self.symtab.display()
  962. if DEBUG > 2: return
  963. arg_ordinal = len(self.function_arguments)
  964. #check argument's type
  965. if not self.symtab.same_type_as_argument(arg.exp, self.function_call_index, arg_ordinal):
  966. raise SemanticException("Incompatible type for argument %d in '%s'" % (arg_ordinal + 1, self.symtab.get_name(self.function_call_index)))
  967. self.function_arguments.append(arg.exp)
  968. def function_call_action(self, text, loc, fun):
  969. """Code executed after recognising the whole function call"""
  970. exshared.setpos(loc, text)
  971. if DEBUG > 0:
  972. print("FUN_CALL:",fun)
  973. if DEBUG == 2: self.symtab.display()
  974. if DEBUG > 2: return
  975. #check number of arguments
  976. if len(self.function_arguments) != self.symtab.get_attribute(self.function_call_index):
  977. raise SemanticException("Wrong number of arguments for function '%s'" % fun.name)
  978. #arguments should be pushed to stack in reverse order
  979. self.function_arguments.reverse()
  980. self.codegen.function_call(self.function_call_index, self.function_arguments)
  981. self.codegen.restore_used_registers()
  982. return_type = self.symtab.get_type(self.function_call_index)
  983. #restore previous function call data
  984. self.function_call_index = self.function_call_stack.pop()
  985. self.function_arguments = self.function_arguments_stack.pop()
  986. register = self.codegen.take_register(return_type)
  987. #move result to a new free register, to allow the next function call
  988. self.codegen.move(self.codegen.take_function_register(return_type), register)
  989. return register
  990. def relexp_action(self, text, loc, arg):
  991. """Code executed after recognising a relexp expression (something relop something)"""
  992. if DEBUG > 0:
  993. print("REL_EXP:",arg)
  994. if DEBUG == 2: self.symtab.display()
  995. if DEBUG > 2: return
  996. exshared.setpos(loc, text)
  997. if not self.symtab.same_types(arg[0], arg[2]):
  998. raise SemanticException("Invalid operands for operator '{0}'".format(arg[1]))
  999. self.codegen.compare(arg[0], arg[2])
  1000. #return relational operator's code
  1001. self.relexp_code = self.codegen.relop_code(arg[1], self.symtab.get_type(arg[0]))
  1002. return self.relexp_code
  1003. def andexp_action(self, text, loc, arg):
  1004. """Code executed after recognising a andexp expression (something and something)"""
  1005. exshared.setpos(loc, text)
  1006. if DEBUG > 0:
  1007. print("AND+EXP:",arg)
  1008. if DEBUG == 2: self.symtab.display()
  1009. if DEBUG > 2: return
  1010. label = self.codegen.label("false{0}".format(self.false_label_number), True, False)
  1011. self.codegen.jump(self.relexp_code, True, label)
  1012. self.andexp_code = self.relexp_code
  1013. return self.andexp_code
  1014. def logexp_action(self, text, loc, arg):
  1015. """Code executed after recognising logexp expression (something or something)"""
  1016. exshared.setpos(loc, text)
  1017. if DEBUG > 0:
  1018. print("LOG_EXP:",arg)
  1019. if DEBUG == 2: self.symtab.display()
  1020. if DEBUG > 2: return
  1021. label = self.codegen.label("true{0}".format(self.label_number), True, False)
  1022. self.codegen.jump(self.relexp_code, False, label)
  1023. self.codegen.newline_label("false{0}".format(self.false_label_number), True, True)
  1024. self.false_label_number += 1
  1025. def if_begin_action(self, text, loc, arg):
  1026. """Code executed after recognising an if statement (if keyword)"""
  1027. exshared.setpos(loc, text)
  1028. if DEBUG > 0:
  1029. print("IF_BEGIN:",arg)
  1030. if DEBUG == 2: self.symtab.display()
  1031. if DEBUG > 2: return
  1032. self.false_label_number += 1
  1033. self.label_number = self.false_label_number
  1034. self.codegen.newline_label("if{0}".format(self.label_number), True, True)
  1035. def if_body_action(self, text, loc, arg):
  1036. """Code executed after recognising if statement's body"""
  1037. exshared.setpos(loc, text)
  1038. if DEBUG > 0:
  1039. print("IF_BODY:",arg)
  1040. if DEBUG == 2: self.symtab.display()
  1041. if DEBUG > 2: return
  1042. #generate conditional jump (based on last compare)
  1043. label = self.codegen.label("false{0}".format(self.false_label_number), True, False)
  1044. self.codegen.jump(self.relexp_code, True, label)
  1045. #generate 'true' label (executes if condition is satisfied)
  1046. self.codegen.newline_label("true{0}".format(self.label_number), True, True)
  1047. #save label numbers (needed for nested if/while statements)
  1048. self.label_stack.append(self.false_label_number)
  1049. self.label_stack.append(self.label_number)
  1050. def if_else_action(self, text, loc, arg):
  1051. """Code executed after recognising if statement's else body"""
  1052. exshared.setpos(loc, text)
  1053. if DEBUG > 0:
  1054. print("IF_ELSE:",arg)
  1055. if DEBUG == 2: self.symtab.display()
  1056. if DEBUG > 2: return
  1057. #jump to exit after all statements for true condition are executed
  1058. self.label_number = self.label_stack.pop()
  1059. label = self.codegen.label("exit{0}".format(self.label_number), True, False)
  1060. self.codegen.unconditional_jump(label)
  1061. #generate final 'false' label (executes if condition isn't satisfied)
  1062. self.codegen.newline_label("false{0}".format(self.label_stack.pop()), True, True)
  1063. self.label_stack.append(self.label_number)
  1064. def if_end_action(self, text, loc, arg):
  1065. """Code executed after recognising a whole if statement"""
  1066. exshared.setpos(loc, text)
  1067. if DEBUG > 0:
  1068. print("IF_END:",arg)
  1069. if DEBUG == 2: self.symtab.display()
  1070. if DEBUG > 2: return
  1071. self.codegen.newline_label("exit{0}".format(self.label_stack.pop()), True, True)
  1072. def while_begin_action(self, text, loc, arg):
  1073. """Code executed after recognising a while statement (while keyword)"""
  1074. exshared.setpos(loc, text)
  1075. if DEBUG > 0:
  1076. print("WHILE_BEGIN:",arg)
  1077. if DEBUG == 2: self.symtab.display()
  1078. if DEBUG > 2: return
  1079. self.false_label_number += 1
  1080. self.label_number = self.false_label_number
  1081. self.codegen.newline_label("while{0}".format(self.label_number), True, True)
  1082. def while_body_action(self, text, loc, arg):
  1083. """Code executed after recognising while statement's body"""
  1084. exshared.setpos(loc, text)
  1085. if DEBUG > 0:
  1086. print("WHILE_BODY:",arg)
  1087. if DEBUG == 2: self.symtab.display()
  1088. if DEBUG > 2: return
  1089. #generate conditional jump (based on last compare)
  1090. label = self.codegen.label("false{0}".format(self.false_label_number), True, False)
  1091. self.codegen.jump(self.relexp_code, True, label)
  1092. #generate 'true' label (executes if condition is satisfied)
  1093. self.codegen.newline_label("true{0}".format(self.label_number), True, True)
  1094. self.label_stack.append(self.false_label_number)
  1095. self.label_stack.append(self.label_number)
  1096. def while_end_action(self, text, loc, arg):
  1097. """Code executed after recognising a whole while statement"""
  1098. exshared.setpos(loc, text)
  1099. if DEBUG > 0:
  1100. print("WHILE_END:",arg)
  1101. if DEBUG == 2: self.symtab.display()
  1102. if DEBUG > 2: return
  1103. #jump to condition checking after while statement body
  1104. self.label_number = self.label_stack.pop()
  1105. label = self.codegen.label("while{0}".format(self.label_number), True, False)
  1106. self.codegen.unconditional_jump(label)
  1107. #generate final 'false' label and exit label
  1108. self.codegen.newline_label("false{0}".format(self.label_stack.pop()), True, True)
  1109. self.codegen.newline_label("exit{0}".format(self.label_number), True, True)
  1110. def program_end_action(self, text, loc, arg):
  1111. """Checks if there is a 'main' function and the type of 'main' function"""
  1112. exshared.setpos(loc, text)
  1113. if DEBUG > 0:
  1114. print("PROGRAM_END:",arg)
  1115. if DEBUG == 2: self.symtab.display()
  1116. if DEBUG > 2: return
  1117. index = self.symtab.lookup_symbol("main",SharedData.KINDS.FUNCTION)
  1118. if index == None:
  1119. raise SemanticException("Undefined reference to 'main'", False)
  1120. elif self.symtab.get_type(index) != SharedData.TYPES.INT:
  1121. self.warning("Return type of 'main' is not int", False)
  1122. def parse_text(self,text):
  1123. """Parse string (helper function)"""
  1124. try:
  1125. return self.rProgram.ignore(cStyleComment).parseString(text, parseAll=True)
  1126. except SemanticException as err:
  1127. print(err)
  1128. exit(3)
  1129. except ParseException as err:
  1130. print(err)
  1131. exit(3)
  1132. def parse_file(self,filename):
  1133. """Parse file (helper function)"""
  1134. try:
  1135. return self.rProgram.ignore(cStyleComment).parseFile(filename, parseAll=True)
  1136. except SemanticException as err:
  1137. print(err)
  1138. exit(3)
  1139. except ParseException as err:
  1140. print(err)
  1141. exit(3)
  1142. ##########################################################################################
  1143. ##########################################################################################
  1144. if 0:
  1145. #main program
  1146. mc = MicroC()
  1147. output_file = "output.asm"
  1148. if len(argv) == 1:
  1149. input_file = stdin
  1150. elif len(argv) == 2:
  1151. input_file = argv[1]
  1152. elif len(argv) == 3:
  1153. input_file = argv[1]
  1154. output_file = argv[2]
  1155. else:
  1156. usage = """Usage: {0} [input_file [output_file]]
  1157. If output file is omitted, output.asm is used
  1158. If input file is omitted, stdin is used""".format(argv[0])
  1159. print(usage)
  1160. exit(1)
  1161. try:
  1162. parse = stdin if input_file == stdin else open(input_file,'r')
  1163. except Exception:
  1164. print("Input file '%s' open error" % input_file)
  1165. exit(2)
  1166. mc.parse_file(parse)
  1167. #if you want to see the final symbol table, uncomment next line
  1168. #mc.symtab.display()
  1169. try:
  1170. out = open(output_file, 'w')
  1171. out.write(mc.codegen.code)
  1172. out.close
  1173. except Exception:
  1174. print("Output file '%s' open error" % output_file)
  1175. exit(2)
  1176. ##########################################################################################
  1177. ##########################################################################################
  1178. if __name__ == "__main__":
  1179. test_program_example = """
  1180. int a;
  1181. int b;
  1182. int c;
  1183. unsigned d;
  1184. int fun1(int x, unsigned y) {
  1185. return 123;
  1186. }
  1187. int fun2(int a) {
  1188. return 1 + a * fun1(a, 456u);
  1189. }
  1190. int main(int x, int y) {
  1191. int w;
  1192. unsigned z;
  1193. if (9 > 8 && 2 < 3 || 6 != 5 && a <= b && c < x || w >= y) {
  1194. a = b + 1;
  1195. if (x == y)
  1196. while (d < 4u)
  1197. x = x * w;
  1198. else
  1199. while (a + b < c - y && x > 3 || y < 2)
  1200. if (z > d)
  1201. a = a - 4;
  1202. else
  1203. b = a * b * c * x / y;
  1204. }
  1205. else
  1206. c = 4;
  1207. a = fun1(x,d) + fun2(fun1(fun2(w + 3 * 2) + 2 * c, 2u));
  1208. return 2;
  1209. }
  1210. """
  1211. mc = MicroC()
  1212. mc.parse_text(test_program_example)
  1213. print(mc.codegen.code)