From 574c2ea2c337e9a2640242572cbf93029e3eec27 Mon Sep 17 00:00:00 2001 From: chyyuu Date: Mon, 27 Jul 2020 15:54:53 +0800 Subject: [PATCH 01/43] Initial commit --- LICENSE | 674 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ README.md | 1 + 2 files changed, 675 insertions(+) create mode 100644 LICENSE create mode 100644 README.md diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..f288702 --- /dev/null +++ b/LICENSE @@ -0,0 +1,674 @@ + GNU GENERAL PUBLIC LICENSE + Version 3, 29 June 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU General Public License is a free, copyleft license for +software and other kinds of works. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. We, the Free Software Foundation, use the +GNU General Public License for most of our software; it applies also to +any other work released this way by its authors. You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you have +certain responsibilities if you distribute copies of the software, or if +you modify it: responsibilities to respect the freedom of others. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, receive +or can get the source code. And you must show them these terms so they +know their rights. + + Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + + For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + + Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the manufacturer +can do so. This is fundamentally incompatible with the aim of +protecting users' freedom to change the software. The systematic +pattern of such abuse occurs in the area of products for individuals to +use, which is precisely where it is most unacceptable. Therefore, we +have designed this version of the GPL to prohibit the practice for those +products. If such problems arise substantially in other domains, we +stand ready to extend this provision to those domains in future versions +of the GPL, as needed to protect the freedom of users. + + Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish to +avoid the special danger that patents applied to a free program could +make it effectively proprietary. To prevent this, the GPL assures that +patents cannot be used to render the program non-free. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Use with the GNU Affero General Public License. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + +Also add information on how to contact you by electronic and paper mail. + + If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + + Copyright (C) + This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, your program's commands +might be different; for a GUI interface, you would use an "about box". + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +. + + The GNU General Public License does not permit incorporating your program +into proprietary programs. If your program is a subroutine library, you +may consider it more useful to permit linking proprietary applications with +the library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. But first, please read +. diff --git a/README.md b/README.md new file mode 100644 index 0000000..4abd25c --- /dev/null +++ b/README.md @@ -0,0 +1 @@ +# minidecaf \ No newline at end of file From 5592aa9b4e3ef82b3ef2c533c81f7386227b184d Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Mon, 27 Jul 2020 16:22:11 +0800 Subject: [PATCH 02/43] add mini-decaf spec --- minidecaf-spec.md | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 minidecaf-spec.md diff --git a/minidecaf-spec.md b/minidecaf-spec.md new file mode 100644 index 0000000..cbd4049 --- /dev/null +++ b/minidecaf-spec.md @@ -0,0 +1,21 @@ +``` +prog : decl+ +decl : vardel | funcdel +vardecl : 'var' ident ':' type ('=' initval)? ';' +type : 'int' | 'bool' | '[' type ']' +funcdecl : 'def' ident '(' argList ')' (':' retTy=type)? blockstmt +argList : (argbinding (',' argbinding)*)? +argbinding : ident ':' type +blockstmt : '{' (stmt (';' stmt)*)? '}' +stmt : blockstmt | vardecl | asgnstmt | skipstmt | ifstmt | whilestmt | exprstmt | returnstmt | intrinsicstmt +asgnstmt : lvalue '=' expr ';' +skipstmt : 'skip' ';' // i.e. pass in python +ifstmt : 'if' '(' expr ')' stmt ('else' stmt)? +whilestmt : 'while' '(' expr ')' stmt +exprstmt : expr ';' +intrinsicstmt : ('print'|'read') exprList ';' +returnstnt : 'return' expr? ';' +lvalue : expr ('[' expr ']') +exprList : (expr (',' expr)*)? +expr : unary / binary / relop / loadstore / arr / paren / cast / literal / newarray / call +``` From 9dbd3c6bc7d6cd3db63d73381642e0d330d7b35e Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Mon, 27 Jul 2020 16:23:58 +0800 Subject: [PATCH 03/43] update mini-decaf spec --- minidecaf-spec.md | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/minidecaf-spec.md b/minidecaf-spec.md index cbd4049..736200b 100644 --- a/minidecaf-spec.md +++ b/minidecaf-spec.md @@ -1,3 +1,5 @@ + +## 基本文法 ``` prog : decl+ decl : vardel | funcdel @@ -19,3 +21,6 @@ lvalue : expr ('[' expr ']') exprList : (expr (',' expr)*)? expr : unary / binary / relop / loadstore / arr / paren / cast / literal / newarray / call ``` + +## feature文法 +小 feature 如 ternary expr ; var 以外加上 val ; 允许 var 做类型推断。 From 5e606b171b9926e14d058f9e8b49272ec57be1ea Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Mon, 27 Jul 2020 16:28:11 +0800 Subject: [PATCH 04/43] hob's first verson of guide-framework --- guide-framework.md | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100644 guide-framework.md diff --git a/guide-framework.md b/guide-framework.md new file mode 100644 index 0000000..d1800b7 --- /dev/null +++ b/guide-framework.md @@ -0,0 +1,9 @@ +# 阶段/指导书 +``` +lexer +parser +namer +typer +codegen +加上每章要有 glue code 解析 +``` From b4dad192d8e99bfffdbb1494637e29f74549b854 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 28 Jul 2020 14:04:27 +0800 Subject: [PATCH 05/43] update doc --- .gitignore | 11 ++++++++ doc/guide-framework.md | 33 ++++++++++++++++++++++ minidecaf-spec.md => doc/minidecaf-spec.md | 2 ++ guide-framework.md | 9 ------ 4 files changed, 46 insertions(+), 9 deletions(-) create mode 100644 .gitignore create mode 100644 doc/guide-framework.md rename minidecaf-spec.md => doc/minidecaf-spec.md (93%) delete mode 100644 guide-framework.md diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d5ec827 --- /dev/null +++ b/.gitignore @@ -0,0 +1,11 @@ +Cargo.lock +target +test/out +*.bak +*.old +*~ +*.org +.idea +*.S +*.s +a.out \ No newline at end of file diff --git a/doc/guide-framework.md b/doc/guide-framework.md new file mode 100644 index 0000000..62ac467 --- /dev/null +++ b/doc/guide-framework.md @@ -0,0 +1,33 @@ +# 实验指导书[框架] + +# 实验简介 + +## minidecaf设计简介 +### 符号表示 +### 开发环境 + +## 编译器面向的计算机 +### CPU与内存 +### 高级语言与汇编语言 +### RISC-V 64简介 + +## 编译器的过程 + +# 创建计算器级语言的编译器 +## 步骤1：有整数表示 +## 步骤2：可执行加减 +## 步骤3：递归下降语法解析 +## 步骤4：有一定的错误提示 +## 步骤5：stack computer on RV64 +## 步骤6：可执行乘除 +## 步骤7：支持括号操作 +## 步骤8：支持一元操作符 +## 步骤9：支持比较操作 + +# 创建可编程级语言的编译器 +## 步骤10：支持变量与赋值语句 +## 步骤11：支持返回语句 +## 步骤12：支持条件语句 +## 步骤13：支持函数 +## 步骤14：支持字符串操作 +## 步骤15：支持数组操作 diff --git a/minidecaf-spec.md b/doc/minidecaf-spec.md similarity index 93% rename from minidecaf-spec.md rename to doc/minidecaf-spec.md index 736200b..83df3e2 100644 --- a/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -1,3 +1,5 @@ +## step1 基本文法 +只有正整数，大致形式是 ` 0;` 或 `5;` ## 基本文法 ``` diff --git a/guide-framework.md b/guide-framework.md deleted file mode 100644 index d1800b7..0000000 --- a/guide-framework.md +++ /dev/null @@ -1,9 +0,0 @@ -# 阶段/指导书 -``` -lexer -parser -namer -typer -codegen -加上每章要有 glue code 解析 -``` From d5052387552f7b8039e4573d3d87fc1e32ed2608 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 28 Jul 2020 14:08:30 +0800 Subject: [PATCH 06/43] update README --- README.md | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/README.md b/README.md index 4abd25c..df3ee22 100644 --- a/README.md +++ b/README.md @@ -1 +1,5 @@ -# minidecaf \ No newline at end of file +# minidecaf + +## status +### 2020.07.28: +- cy: step 11 finished. From 40b7050906de3150a5454ed3f821f1a045a22bc6 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 28 Jul 2020 17:14:10 +0800 Subject: [PATCH 07/43] update minidecaf-spec --- doc/minidecaf-spec.md | 138 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 135 insertions(+), 3 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 83df3e2..effe1d4 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -1,7 +1,139 @@ -## step1 基本文法 -只有正整数，大致形式是 ` 0;` 或 `5;` -## 基本文法 +- * means the preceding element is repeated zero or more times +- + means one or more repeats +- ? means optional(zero or one) + +## 步骤1：有整数表示 +只有正整数，大致形式是 `0` 或 `5` +``` +digit = [0-9] +``` +## 步骤2：可执行加减 +``` +expr= term ("+" term | "-" term)* +term = num +num = digit+ +digit = [0-9] +``` +## 步骤3：递归下降语法解析 +``` +factor = digit {addop digit} +digit = [0-9] +addop = "+" | "-" +``` +## 步骤4：有一定的错误提示 +``` +expr= term ("+" term | "-" term)* +term = num +num = digit+ +digit = [0-9] +``` +## 步骤5：stack computer on RV64 +``` +expr= term ("+" term | "-" term)* +term = num +num = digit+ +digit = [0-9] +``` +## 步骤6：可执行乘除 +``` +expr= term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = num +num = digit+ +digit = [0-9] +``` +## 步骤7：支持括号操作 +``` +expr= term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = num | "(" expr ")" +num = digit+ +digit = [0-9] +``` +## 步骤8：支持一元操作符 + +``` +expr= term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +``` + +## 步骤9：支持比较操作 + +``` +expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +``` +## 步骤10：支持变量与赋值语句 +``` +stmt = (var "=" expr ";")+ +expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +var= ident "=" expr +ident = [a-z]+[a-z0-9_]* +``` + +## 步骤11：支持返回语句 +``` +stmt = ("return" expr ";" | var "=" expr ";")+ +expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +var= ident "=" expr +ident = [a-z]+[a-z0-9_]* +``` + +## 步骤12：支持条件语句 +``` +stmt = ("return" expr ";" | var "=" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? ";" | "{" stmt* "}" ";")+ +expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +var= ident "=" expr +ident = [a-z]+[a-z0-9_]* +``` + +## 步骤13：支持函数 +``` +function = ident "(" ")" "{" stmt "}" +stmt = ("return" expr ";" | var "=" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? ";" | "{" stmt* "}" ";")+ +expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* +term = factor ("*" factor | "/" factor)* +factor = unary? (num | "(" expr ")") +num = digit+ +digit = [0-9] +unary = "+" | "-" +var= ident "=" expr +ident = [a-z]+[a-z0-9_]* +``` + +## 步骤14：支持字符串操作 +缺 int, char* 定义和相关操作 + +## 步骤15：支持数组操作 +缺 arry的定义和相关操作 + +## 步骤X：完整的基本文法 + +缺ARRAY, String，与前面的不太一致 ``` prog : decl+ decl : vardel | funcdel From b95051318eb77140c896afd0cdc0ab12cb1f1c5e Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 28 Jul 2020 17:23:18 +0800 Subject: [PATCH 08/43] update spec, need more work on spec --- doc/minidecaf-spec.md | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index effe1d4..ac586b1 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -129,11 +129,23 @@ ident = [a-z]+[a-z0-9_]* 缺 int, char* 定义和相关操作 ## 步骤15：支持数组操作 -缺 arry的定义和相关操作 +缺 array的定义和相关操作 + +> 备注 对于第14、15步，需要实现： + +1. 一元`&`：返回变量地址和一元`*`：返回地址指向的值 +1. 删除隐式变量定义并引入关键字int +1. 实现指针加法和减法 +1. sizeof运算符 +1. 实现数组 +1. 实现数组下标 +1. 全局变量 +1. 字符类型 +1. 字符串字面量 ## 步骤X：完整的基本文法 -缺ARRAY, String，与前面的不太一致 +缺ARRAY, String等，与前面的不太一致 ``` prog : decl+ decl : vardel | funcdel From b9e9372939b364a8f69bb64acad303d341b28e4d Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 28 Jul 2020 18:37:48 +0800 Subject: [PATCH 09/43] update minidecaf spec --- doc/minidecaf-spec.md | 49 ++++++++++++++++++++++++------------------- 1 file changed, 28 insertions(+), 21 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index ac586b1..6abec93 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -145,27 +145,34 @@ ident = [a-z]+[a-z0-9_]* ## 步骤X：完整的基本文法 -缺ARRAY, String等，与前面的不太一致 -``` -prog : decl+ -decl : vardel | funcdel -vardecl : 'var' ident ':' type ('=' initval)? ';' -type : 'int' | 'bool' | '[' type ']' -funcdecl : 'def' ident '(' argList ')' (':' retTy=type)? blockstmt -argList : (argbinding (',' argbinding)*)? -argbinding : ident ':' type -blockstmt : '{' (stmt (';' stmt)*)? '}' -stmt : blockstmt | vardecl | asgnstmt | skipstmt | ifstmt | whilestmt | exprstmt | returnstmt | intrinsicstmt -asgnstmt : lvalue '=' expr ';' -skipstmt : 'skip' ';' // i.e. pass in python -ifstmt : 'if' '(' expr ')' stmt ('else' stmt)? -whilestmt : 'while' '(' expr ')' stmt -exprstmt : expr ';' -intrinsicstmt : ('print'|'read') exprList ';' -returnstnt : 'return' expr? ';' -lvalue : expr ('[' expr ']') -exprList : (expr (',' expr)*)? -expr : unary / binary / relop / loadstore / arr / paren / cast / literal / newarray / call +mini-decaf几乎就是一个C子集 +下面的内容可能有bug +``` +program = toplv* +toplv = typ ident ("(" (typ ident ("," typ ident)*)? ")" "{" stmt* "}" | ("[" num "]")* ";") +stmt = expr ";" + | "{" stmt* "}" + | "if" "(" expr ")" stmt ("else" stmt)? + | "while" "(" expr ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt + | "return" expr ";" + | typ ident ("[" num "]")* ";" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = "+"? primary + | "-"? primary + | "&" unary + | "*" unary + | "sizeof" unary + | primary "[" expr "]" +primary = num + | ident ("(" (expr ("," expr)*)? ")")? + | "(" expr ")" +typ = ("int" | "char") "*"* ``` ## feature文法 From cbadf8d8a0b2d9b5e675315837c07e7955e63cf8 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Wed, 29 Jul 2020 18:50:35 +0800 Subject: [PATCH 10/43] update minidcaf spec --- doc/minidecaf-spec.md | 186 +++++++++++++++++++++++++++++------------- 1 file changed, 131 insertions(+), 55 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 6abec93..cc40b2e 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -10,129 +10,172 @@ digit = [0-9] ``` ## 步骤2：可执行加减 ``` -expr= term ("+" term | "-" term)* -term = num +expr= num ("+" num | "-" num)* num = digit+ digit = [0-9] ``` ## 步骤3：递归下降语法解析 ``` -factor = digit {addop digit} +expr= num ("+" num | "-" num)* +num = digit+ digit = [0-9] -addop = "+" | "-" ``` ## 步骤4：有一定的错误提示 ``` -expr= term ("+" term | "-" term)* -term = num +expr= num ("+" num | "-" num)* num = digit+ digit = [0-9] ``` ## 步骤5：stack computer on RV64 ``` -expr= term ("+" term | "-" term)* -term = num +expr= num ("+" num | "-" num)* num = digit+ digit = [0-9] ``` ## 步骤6：可执行乘除 ``` -expr= term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = num +expr = mul ("+" mul | "-" mul)* +mul = num ("*" num | "/" num)* num = digit+ digit = [0-9] ``` ## 步骤7：支持括号操作 ``` -expr= term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = num | "(" expr ")" +expr = mul ("+" mul | "-" mul)* +mul = primary ("*" primary | "/" primary)* +primary = num | "(" expr ")" num = digit+ digit = [0-9] ``` ## 步骤8：支持一元操作符 ``` -expr= term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +expr = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" ``` ## 步骤9：支持比较操作 ``` -expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +expr = equality +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" ``` ## 步骤10：支持变量与赋值语句 ``` -stmt = (var "=" expr ";")+ -expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +program = stmt* +stmt = expr ";" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | ident | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" -var= ident "=" expr ident = [a-z]+[a-z0-9_]* ``` ## 步骤11：支持返回语句 ``` -stmt = ("return" expr ";" | var "=" expr ";")+ -expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +program = stmt* +stmt = expr ";" + | "return" expr ";" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | ident | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" -var= ident "=" expr ident = [a-z]+[a-z0-9_]* ``` ## 步骤12：支持条件语句 ``` -stmt = ("return" expr ";" | var "=" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? ";" | "{" stmt* "}" ";")+ -expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +program = stmt* +stmt = expr ";" + | "return" expr ";" + | "if" "(" expr ")" stmt ("else" stmt)? + | "while" "(" expr ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | ident | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" -var= ident "=" expr ident = [a-z]+[a-z0-9_]* ``` -## 步骤13：支持函数 +## 步骤13：支持语句块和函数 +支持语句块 +``` +program = stmt* +stmt = expr ";" + | "return" expr ";" + | "if" "(" expr ")" stmt ("else" stmt)? + | "while" "(" expr ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt + | "{" stmt* "}" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num | ident | "(" expr ")" +num = digit+ +digit = [0-9] +ident = [a-z]+[a-z0-9_]* ``` -function = ident "(" ")" "{" stmt "}" -stmt = ("return" expr ";" | var "=" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? ";" | "{" stmt* "}" ";")+ -expr = expr "==" expr | expr "!=" expr | expr "<" expr | expr "<=" expr | expr ">" expr | expr ">=" expr | term ("+" term | "-" term)* -term = factor ("*" factor | "/" factor)* -factor = unary? (num | "(" expr ")") +支持函数 +``` +program = stmt* +stmt = expr ";" + | "return" expr ";" + | "if" "(" expr ")" stmt ("else" stmt)? + | "while" "(" expr ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt + | "{" stmt* "}" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = ("+" | "-")? primary +primary = num + | ident ("(" ")")? + | "(" expr ")" num = digit+ digit = [0-9] -unary = "+" | "-" -var= ident "=" expr ident = [a-z]+[a-z0-9_]* ``` -## 步骤14：支持字符串操作 -缺 int, char* 定义和相关操作 - -## 步骤15：支持数组操作 -缺 array的定义和相关操作 - -> 备注 对于第14、15步，需要实现： +## 步骤14/15/.../X：支持字符串操作/支持数组操作等 +需要如下步骤 1. 一元`&`：返回变量地址和一元`*`：返回地址指向的值 1. 删除隐式变量定义并引入关键字int 1. 实现指针加法和减法 @@ -142,6 +185,39 @@ ident = [a-z]+[a-z0-9_]* 1. 全局变量 1. 字符类型 1. 字符串字面量 +1. ... + +``` +program = toplv* +toplv = typ ident ("(" (typ ident ("," typ ident)*)? ")" "{" stmt* "}" | ("[" num "]")* ";") +stmt = expr ";" + | "{" stmt* "}" + | "if" "(" expr ")" stmt ("else" stmt)? + | "while" "(" expr ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt + | "return" expr ";" + | typ ident ("[" num "]")* ";" +expr = assign +assign = equality ("=" assign)? +equality = relational ("==" relational | "!=" relational)* +relational = add ("<" add | "<=" add | ">" add | ">=" add)* +add = mul ("+" mul | "-" mul)* +mul = unary ("*" unary | "/" unary)* +unary = "+"? primary + | "-"? primary + | "&" unary + | "*" unary + | "sizeof" unary + | primary "[" expr "]" +primary = num + | ident ("(" (expr ("," expr)*)? ")")? + | "(" expr ")" +typ = ("int" | "char") "*"* +num = digit+ +digit = [0-9] +ident = [a-z]+[a-z0-9_]* +``` + ## 步骤X：完整的基本文法 From 0ae7fd6e23bac2e1bab20094ef27d1212af75242 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Fri, 31 Jul 2020 08:40:15 +0800 Subject: [PATCH 11/43] add test for step15 --- test/test-step15.sh | 169 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 169 insertions(+) create mode 100755 test/test-step15.sh diff --git a/test/test-step15.sh b/test/test-step15.sh new file mode 100755 index 0000000..ac7ae39 --- /dev/null +++ b/test/test-step15.sh @@ -0,0 +1,169 @@ +#!/bin/bash +cat < out/asm.S #change YOUR Compiler to build asm.S + + riscv64-unknown-elf-gcc out/asm.S tmp2.o -o out/run + qemu-riscv64 out/run + + res=$? + + if [ $res == $ans ]; then + echo "OK! Result: $res, Ans: $ans" + else + echo -e "\033[0;31mNG\033[0;39m" + echo "FAIL! Result: $res, Ans: $ans" + exit 1 + fi +} + +assert 0 'int main() { return 0; }' +assert 42 'int main() { return 42; }' +assert 21 'int main() { return 5+20-4; }' +assert 41 'int main() { return 12 + 34 - 5 ; }' +assert 47 'int main() { return 5+6*7; }' +assert 15 'int main() { return 5*(9-6); }' +assert 4 'int main() { return (3+5)/2; }' +assert 10 'int main() { return -10+20; }' +assert 10 'int main() { return - -10; }' +assert 10 'int main() { return - - +10; }' + +assert 0 'int main() { return 0==1; }' +assert 1 'int main() { return 42==42; }' +assert 1 'int main() { return 0!=1; }' +assert 0 'int main() { return 42!=42; }' + +assert 1 'int main() { return 0<1; }' +assert 0 'int main() { return 1<1; }' +assert 0 'int main() { return 2<1; }' +assert 1 'int main() { return 0<=1; }' +assert 1 'int main() { return 1<=1; }' +assert 0 'int main() { return 2<=1; }' + +assert 1 'int main() { return 1>0; }' +assert 0 'int main() { return 1>1; }' +assert 0 'int main() { return 1>2; }' +assert 1 'int main() { return 1>=0; }' +assert 1 'int main() { return 1>=1; }' +assert 0 'int main() { return 1>=2; }' + +assert 3 'int main() { int a; a=3; return a; }' +assert 8 'int main() { int a; int z; a=3; z=5; return a+z; }' +assert 3 'int main() { int a=3; return a; }' +assert 8 'int main() { int a=3; int z=5; return a+z; }' + +assert 1 'int main() { return 1; 2; 3; }' +assert 2 'int main() { 1; return 2; 3; }' +assert 3 'int main() { 1; 2; return 3; }' + +assert 3 'int main() { int foo=3; return foo; }' +assert 8 'int main() { int foo123=3; int bar=5; return foo123+bar; }' + +assert 3 'int main() { if (0) return 2; return 3; }' +assert 3 'int main() { if (1-1) return 2; return 3; }' +assert 2 'int main() { if (1) return 2; return 3; }' +assert 2 'int main() { if (2-1) return 2; return 3; }' + +assert 3 'int main() { {1; {2;} return 3;} }' + +assert 10 'int main() { int i=0; i=0; while(i<10) i=i+1; return i; }' +assert 55 'int main() { int i=0; int j=0; while(i<=10) {j=i+j; i=i+1;} return j; }' + +assert 55 'int main() { int i=0; int j=0; for (i=0; i<=10; i=i+1) j=i+j; return j; }' +assert 3 'int main() { for (;;) return 3; return 5; }' + +assert 3 'int main() { return ret3(); }' +assert 5 'int main() { return ret5(); }' +assert 8 'int main() { return add(3, 5); }' +assert 2 'int main() { return sub(5, 3); }' +assert 21 'int main() { return add6(1,2,3,4,5,6); }' + +assert 32 'int main() { return ret32(); } int ret32() { return 32; }' +assert 7 'int main() { return add2(3,4); } int add2(int x, int y) { return x+y; }' +assert 1 'int main() { return sub2(4,3); } int sub2(int x, int y) { return x-y; }' +assert 55 'int main() { return fib(9); } int fib(int x) { if (x<=1) return 1; return fib(x-1) + fib(x-2); }' + +assert 3 'int main() { int x=3; return *&x; }' +assert 3 'int main() { int x=3; int *y=&x; int **z=&y; return **z; }' +assert 5 'int main() { int x=3; int y=5; return *(&x+1); }' +assert 5 'int main() { int x=3; int y=5; return *(1+&x); }' +assert 3 'int main() { int x=3; int y=5; return *(&y-1); }' +assert 5 'int main() { int x=3; int y=5; int *z=&x; return *(z+1); }' +assert 3 'int main() { int x=3; int y=5; int *z=&y; return *(z-1); }' +assert 5 'int main() { int x=3; int *y=&x; *y=5; return x; }' +assert 7 'int main() { int x=3; int y=5; *(&x+1)=7; return y; }' +assert 7 'int main() { int x=3; int y=5; *(&y-1)=7; return x; }' +assert 8 'int main() { int x=3; int y=5; return foo(&x, y); } int foo(int *x, int y) { return *x + y; }' + +assert 3 'int main() { int x[2]; int *y=&x; *y=3; return *x; }' + +assert 3 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *x; }' +assert 4 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *(x+1); }' +assert 5 'int main() { int x[3]; *x=3; *(x+1)=4; *(x+2)=5; return *(x+2); }' + +assert 0 'int main() { int x[2][3]; int *y=x; *y=0; return **x; }' +assert 1 'int main() { int x[2][3]; int *y=x; *(y+1)=1; return *(*x+1); }' +assert 2 'int main() { int x[2][3]; int *y=x; *(y+2)=2; return *(*x+2); }' +assert 3 'int main() { int x[2][3]; int *y=x; *(y+3)=3; return **(x+1); }' +assert 4 'int main() { int x[2][3]; int *y=x; *(y+4)=4; return *(*(x+1)+1); }' +assert 5 'int main() { int x[2][3]; int *y=x; *(y+5)=5; return *(*(x+1)+2); }' +assert 6 'int main() { int x[2][3]; int *y=x; *(y+6)=6; return **(x+2); }' + +assert 3 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *x; }' +assert 4 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+1); }' +assert 5 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+2); }' +assert 5 'int main() { int x[3]; *x=3; x[1]=4; x[2]=5; return *(x+2); }' +assert 5 'int main() { int x[3]; *x=3; x[1]=4; 2[x]=5; return *(x+2); }' + +assert 0 'int main() { int x[2][3]; int *y=x; y[0]=0; return x[0][0]; }' +assert 1 'int main() { int x[2][3]; int *y=x; y[1]=1; return x[0][1]; }' +assert 2 'int main() { int x[2][3]; int *y=x; y[2]=2; return x[0][2]; }' +assert 3 'int main() { int x[2][3]; int *y=x; y[3]=3; return x[1][0]; }' +assert 4 'int main() { int x[2][3]; int *y=x; y[4]=4; return x[1][1]; }' +assert 5 'int main() { int x[2][3]; int *y=x; y[5]=5; return x[1][2]; }' +assert 6 'int main() { int x[2][3]; int *y=x; y[6]=6; return x[2][0]; }' + +assert 8 'int main() { int x; return sizeof(x); }' +assert 8 'int main() { int x; return sizeof x; }' +assert 8 'int main() { int *x; return sizeof(x); }' +assert 32 'int main() { int x[4]; return sizeof(x); }' +assert 96 'int main() { int x[3][4]; return sizeof(x); }' +assert 32 'int main() { int x[3][4]; return sizeof(*x); }' +assert 8 'int main() { int x[3][4]; return sizeof(**x); }' +assert 9 'int main() { int x[3][4]; return sizeof(**x) + 1; }' +assert 9 'int main() { int x[3][4]; return sizeof **x + 1; }' +assert 8 'int main() { int x[3][4]; return sizeof(**x + 1); }' + +assert 0 'int x; int main() { return x; }' +assert 3 'int x; int main() { x=3; return x; }' +assert 0 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[0]; }' +assert 1 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[1]; }' +assert 2 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[2]; }' +assert 3 'int x[4]; int main() { x[0]=0; x[1]=1; x[2]=2; x[3]=3; return x[3]; }' + +assert 8 'int x; int main() { return sizeof(x); }' +assert 32 'int x[4]; int main() { return sizeof(x); }' + +assert 1 'int main() { char x=1; return x; }' +assert 1 'int main() { char x=1; char y=2; return x; }' +assert 2 'int main() { char x=1; char y=2; return y; }' + +assert 1 'int main() { char x; return sizeof(x); }' +assert 10 'int main() { char x[10]; return sizeof(x); }' +assert 1 'int main() { return sub_char(7, 3, 3); } int sub_char(char a, char b, char c) { return a-b-c; }' + +echo OK From c7d956cd351085b3c1a8f453d6ed58e127b4630d Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Sun, 2 Aug 2020 19:41:04 +0800 Subject: [PATCH 12/43] add riscv assembly info --- doc/riscv-32bit-64bit-diffs.md | 52 ++++++ doc/riscv-assembly-directives.md | 23 +++ doc/riscv-assembly-intro.md | 100 +++++++++++ doc/riscv-instructions.md | 276 +++++++++++++++++++++++++++++++ 4 files changed, 451 insertions(+) create mode 100644 doc/riscv-32bit-64bit-diffs.md create mode 100644 doc/riscv-assembly-directives.md create mode 100644 doc/riscv-assembly-intro.md create mode 100644 doc/riscv-instructions.md diff --git a/doc/riscv-32bit-64bit-diffs.md b/doc/riscv-32bit-64bit-diffs.md new file mode 100644 index 0000000..273dba7 --- /dev/null +++ b/doc/riscv-32bit-64bit-diffs.md @@ -0,0 +1,52 @@ +Unfortunately, 64 bit RISC-V is not directly compatible with 32 bit RISC-V. The semantics of `add`, and other arithmetic instructions change to work on the whole 64 bit registers rather than just the 32 bits that the 32 bit version would operate on. The "w" suffix instructions, mimic the behavior of the 32 bit versions of instructions and sign extend the top 32 bits. + +Shifts are also a little different. Shifts consider 1 more bit to determine how far to shift. This allows them to shift an extra 32 bits. Immediate shifts allow encoding an additional bit as well. + +### 64 bit only instructions + +| Example Usage | Description | +|---------------|-------------| +|addiw t1,t2,-100|Addition immediate: set t1 to (t2 plus signed 12-bit immediate) using only the lower 32 bits| +|addw t1,t2,t3|Addition: set t1 to (t2 plus t3) using only the lower 32 bits| +|divuw t1,t2,t3|Division: set t1 to the result of t2/t3 using unsigned division limited to 32 bits| +|divw t1,t2,t3|Division: set t1 to the result of t2/t3 using only the lower 32 bits| +|fcvt.d.l f1, t1, dyn|Convert double from long: Assigns the value of t1 to f1| +|fcvt.d.lu f1, t1, dyn|Convert double from unsigned long: Assigns the value of t1 to f1| +|fcvt.l.d t1, f1, dyn|Convert 64 bit integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.l.s t1, f1, dyn|Convert 64 bit integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.lu.d t1, f1, dyn|Convert unsigned 64 bit integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.lu.s t1, f1, dyn|Convert unsigned 64 bit integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.s.l f1, t1, dyn|Convert float from long: Assigns the value of t1 to f1| +|fcvt.s.lu f1, t1, dyn|Convert float from unsigned long: Assigns the value of t1 to f1| +|fmv.d.x f1, t1|Move float: move bits representing a double from an 64 bit integer register| +|fmv.x.d t1, f1|Move double: move bits representing a double to an 64 bit integer register| +|ld t1, -100(t2)|Set t1 to contents of effective memory double word address| +|lwu t1, -100(t2)|Set t1 to contents of effective memory word address without sign-extension| +|mulw t1,t2,t3|Multiplication: set t1 to the lower 32 bits of t2*t3 using only the lower 32 bits of the input| +|remuw t1,t2,t3|Remainder: set t1 to the remainder of t2/t3 using unsigned division limited to 32 bits| +|remw t1,t2,t3|Remainder: set t1 to the remainder of t2/t3 using only the lower 32 bits| +|sd t1, -100(t2)|Store double word : Store contents of t1 into effective memory double word address| +|slli t1,t2,33|Shift left logical : Set t1 to result of shifting t2 left by number of bits specified by immediate| +|slliw t1,t2,10|Shift left logical (32 bit): Set t1 to result of shifting t2 left by number of bits specified by immediate| +|sllw t1,t2,t3|Shift left logical (32 bit): Set t1 to result of shifting t2 left by number of bits specified by value in low-order 5 bits of t3| +|srai t1,t2,33|Shift right arithmetic : Set t1 to result of sign-extended shifting t2 right by number of bits specified by immediate| +|sraiw t1,t2,10|Shift right arithmetic (32 bit): Set t1 to result of sign-extended shifting t2 right by number of bits specified by immediate| +|sraw t1,t2,t3|Shift left logical (32 bit): Set t1 to result of shifting t2 left by number of bits specified by value in low-order 5 bits of t3| +|srli t1,t2,33|Shift right logical : Set t1 to result of shifting t2 right by number of bits specified by immediate| +|srliw t1,t2,10|Shift right logical (32 bit): Set t1 to result of shifting t2 right by number of bits specified by immediate| +|srlw t1,t2,t3|Shift left logical (32 bit): Set t1 to result of shifting t2 left by number of bits specified by value in low-order 5 bits of t3| +|subw t1,t2,t3|Subtraction: set t1 to (t2 minus t3) using only the lower 32 bits| + +### 64 bit only psuedo-instructions: + +| Example Usage | Description | +|---------------|-------------| +|fcvt.d.l f1, t1 |Convert double from signed 64 bit integer: Assigns the value of t1 to f1| +|fcvt.d.lu f1, t1 |Convert double from unsigned 64 bit integer: Assigns the value of t1 to f1| +|fcvt.l.d t1, f1 |Convert signed 64 bit integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.l.s t1, f1 |Convert signed 64 bit integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.lu.d t1, f1 |Convert unsigned 64 bit integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.lu.s t1, f1 |Convert unsigned 64 bit integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.s.l f1, t1 |Convert float from signed 64 bit integer: Assigns the value of t1 to f1| +|fcvt.s.lu f1, t1 |Convert float from unsigned 64 bit integer: Assigns the value of t1 to f1| +|li t1,1000000000000000 |Load Immediate : Set t1 to 64-bit immediate| \ No newline at end of file diff --git a/doc/riscv-assembly-directives.md b/doc/riscv-assembly-directives.md new file mode 100644 index 0000000..1e4a620 --- /dev/null +++ b/doc/riscv-assembly-directives.md @@ -0,0 +1,23 @@ +The currently supported directives are: + +| Name | Description| +|------|------------| +|.align|Align next data item on specified byte boundary (0=byte, 1=half, 2=word, 3=double)| +|.ascii|Store the string in the Data segment but do not add null terminator| +|.asciz|Store the string in the Data segment and add null terminator| +|.byte|Store the listed value(s) as 8 bit bytes| +|.data|Subsequent items stored in Data segment at next available address| +|.double|Store the listed value(s) as double precision floating point| +|.end_macro|End macro definition. See .macro| +|.eqv|Substitute second operand for first. First operand is symbol, second operand is expression (like #define)| +|.extern|Declare the listed label and byte length to be a global data field| +|.float|Store the listed value(s) as single precision floating point| +|.globl|Declare the listed label(s) as global to enable referencing from other files| +|.half|Store the listed value(s) as 16 bit halfwords on halfword boundary| +|.include|Insert the contents of the specified file. Put filename in quotes.| +|.macro|Begin macro definition. See .end_macro| +|.section|Allows specifying sections without .text or .data directives. Included for gcc comparability| +|.space|Reserve the next specified number of bytes in Data segment| +|.string|Alias for .asciz| +|.text|Subsequent items (instructions) stored in Text segment at next available address| +|.word|Store the listed value(s) as 32 bit words on word boundary| diff --git a/doc/riscv-assembly-intro.md b/doc/riscv-assembly-intro.md new file mode 100644 index 0000000..ae5fc17 --- /dev/null +++ b/doc/riscv-assembly-intro.md @@ -0,0 +1,100 @@ +The [first tutorial](Creating-Hello-World) doesn't explain enough of the core concepts needed to move on to more complicated programs. This page will dig deeper into RISC-V, and explain the fundamentals required for you to write your own "hello world" program. + +## Registers + +Registers are the variables of assembly. However, unlike in high level languages, we have a limited number (32) of registers. Registers are used to store information that will be needed quickly; long-lasting values generally are stored in RAM. + +In RISC-V, we can only directly manipulate registers. If you want to modify something in RAM you must load it into a register, modify it, and then write the value back to RAM. + +There are two ways to refer to each register: its proper name `x0`, `x1`, ..., `x31` and its [ABI](https://en.wikipedia.org/wiki/Application_binary_interface) name `zero`, `ra`, ..., `t6`. The ABI names refer to things like "return address" and "temporary 6". For more information about that, check out the [calling convention page](Calling-Convention). The only special register is `x0`/`zero`, which always has the value 0 and ignores being written to. + +## Instructions + +All code that is executed in a RISC-V processor comes in the form of instructions. Things like adding/multiplying two numbers, loading a value from RAM into a register, and issuing a system call are instructions. There is no fundamental concept of a function, loop, or if statement; all of those concepts are made using instructions. + +For example, the following executes the `addi` instruction 10 times. + +``` + li t0, 10 # t0 = 10 + li t1, 0 # t1 = 0 +loop: + addi t1, t1, 1 # add t1 += 1 + bne t0, t1, loop # Branch to the loop label if t0 == t1 +``` + +A full list of instructions supported by RARS is available [here](Supported-Instructions). + +### Immediates and Labels + +Nearly every instruction involves a register, but some also use a number or label. This is often referred to as an immediate. Immediates are stored as part of the instruction in the form of a number. When assembling the program, the label's address - the instruction's address is used as the immediate. + +The use of labels like `loop` in the small program above is not strictly necessary. You could write the instructions directly doing that, but it would be very time consuming to write. + +_Note: RARS doesn't actually support hardcoding offset immediates, but it would work in GCC._ + +### Psuedo-Instructions + +RISC-V is a [RISC](https://en.wikipedia.org/wiki/Reduced_instruction_set_computer) instruction set, and therefore tries to minimize instructions. So there isn't an instruction dedicated to loading a value into a register, or to move a value from one register to another. However, many instructions that might be nice to have can be made using other instructions. We call these instructions (that aren't in the instruction set, but can be directly replace with real instructions) psuedo-instructions. + +For example, `li t0, 10` can be translated into `addi t0, zero, 10`. + +## Assembler Directives + +Assembler directives are a way of telling the assembler what to put in the executable besides instructions. It allows you to set up memory for when your program starts running. All directives start with a `.` like `.data` or `.macro`. + +I'll explain the most common ones, but a full list of the directives is available [here](Assembler-Directives). + +### Text vs Data + +Easily the most important directives are `.text` and `.data`; these tell the assembler where to store the instructions or data that follow. The `.text` section stores instructions and the `.data` section stores (global) variables we will be using and starts with them initialized. + +Because code and data become bytes before a program starts, we need to tell the assembler in what section to put code. Both directives can also be used to tell the assembler exactly where to put data/code in the section. This can be done by appending an address after the directive like `.text 0x400010`, but this is generally not necessary. + +There are also subtle differences between the `.data` and `.text` sections that can be disabled in RARS by enabling self-modifying code. More about that can be found in [a later explanation](Sections-and-Permissions). + +### Initializing data + +Generally, there are four types of data that can be set up after a `.data` directive: integers, floating point numbers, strings, and allocated space for the program to fill later. + +Integers can be initialized with `.byte`, `.half`, and `.word` for 1 byte, 2 byte, and 4 byte integers, respectively. They can also store multiple comma-separated values. + +For example: +``` +.data +big: + .word 0x1000000 +medium: + .half 0x1000 +smalls: + .byte 0x10, 90, -10 +``` + +Floating point numbers can be initialized with `.float`. The number is stored as the closest IEEE 754 floating point number. `NaN` and `Inf` can be used to represent "Not a Number" and Infinity, respectively. Like with integers, it can store multiple values. + +For example: +``` +.float 90, NaN, -Inf, -1.337, 1e10 +``` + +There are two flavors of strings: those automatically ending with a NULL (0) byte, and those that are not. `.asciz` or `.string` is used for the former, and `.ascii` is used for the latter. Despite what the names would imply, the directives actually store the strings encoded as [UTF-8](https://en.wikipedia.org/wiki/UTF-8) characters. However, because UTF-8 is backward-compatible with [ASCII](https://en.wikipedia.org/wiki/ASCII), the correct characters/strings are stored. + +For example, the following all put the same string into memory: +``` +ASCIZ: +.asciz "Hello" +ASCII: +.ascii "Hello\0" +BYTES: +.byte 0x48, 0x65, 0x6C, 0x6C, 0x6F, 0 +. +``` + +Finally, the last way to set up memory is to allocate space only filled with zeroes. The main way to do this is using the `.space` directive. `.space 10` will allocate ten bytes of space. The other way is to use `.extern`; it allows multiple files to define the same variable without duplicating it. This would generally be used in a file that is included using `.include` so that multiple files including the same file don't duplicate it in memory. + +``` +.extern LABEL, 90 # allocates 90 bytes that can be referenced by LABEL +``` + + + + diff --git a/doc/riscv-instructions.md b/doc/riscv-instructions.md new file mode 100644 index 0000000..9460139 --- /dev/null +++ b/doc/riscv-instructions.md @@ -0,0 +1,276 @@ +RARS supports all instruction in RV32imfd. Additionally it supports `uret` from extension n, and `wfi` from the privileged specification. rv64 mode instructions are not included here and instead have their own page [[Differences between 32 bit and 64 bit modes]]. Fence instructions do nothing as RARS doesn't have a cache. + +If there is an instruction from RV32imfd missing, that's a bug. Additionally, all psuedo-instructions listed in the spec should also be supported. + +| Example Usage | Description | +|---------------|-------------| +|add t1,t2,t3|Addition: set t1 to (t2 plus t3)| +|addi t1,t2,-100|Addition immediate: set t1 to (t2 plus signed 12-bit immediate)| +|and t1,t2,t3|Bitwise AND : Set t1 to bitwise AND of t2 and t3| +|andi t1,t2,-100|Bitwise AND immediate : Set t1 to bitwise AND of t2 and sign-extended 12-bit immediate| +|auipc t1,100000|Add upper immediate to pc: set t1 to (pc plus an upper 20-bit immediate)| +|beq t1,t2,label|Branch if equal : Branch to statement at label's address if t1 and t2 are equal| +|bge t1,t2,label|Branch if greater than or equal: Branch to statement at label's address if t1 is greater than or equal to t2| +|bgeu t1,t2,label|Branch if greater than or equal to (unsigned): Branch to statement at label's address if t1 is greater than or equal to t2 (with an unsigned interpretation)| +|blt t1,t2,label|Branch if less than: Branch to statement at label's address if t1 is less than t2| +|bltu t1,t2,label|Branch if less than (unsigned): Branch to statement at label's address if t1 is less than t2 (with an unsigned interpretation)| +|bne t1,t2,label|Branch if not equal : Branch to statement at label's address if t1 and t2 are not equal| +|csrrc t0, fcsr, t1|Atomic Read/Clear CSR: read from the CSR into t0 and clear bits of the CSR according to t1| +|csrrci t0, fcsr, 10|Atomic Read/Clear CSR Immediate: read from the CSR into t0 and clear bits of the CSR according to a constant| +|csrrs t0, fcsr, t1|Atomic Read/Set CSR: read from the CSR into t0 and logical or t1 into the CSR| +|csrrsi t0, fcsr, 10|Atomic Read/Set CSR Immediate: read from the CSR into t0 and logical or a constant into the CSR| +|csrrw t0, fcsr, t1|Atomic Read/Write CSR: read from the CSR into t0 and write t1 into the CSR| +|csrrwi t0, fcsr, 10|Atomic Read/Write CSR Immediate: read from the CSR into t0 and write a constant into the CSR| +|div t1,t2,t3|Division: set t1 to the result of t2/t3| +|divu t1,t2,t3|Division: set t1 to the result of t2/t3 using unsigned division| +|ebreak|Pause execution| +|ecall|Issue a system call : Execute the system call specified by value in a7| +|fadd.d f1, f2, f3, dyn|Floating ADD (64 bit): assigns f1 to f2 + f3| +|fadd.s f1, f2, f3, dyn|Floating ADD: assigns f1 to f2 + f3| +|fclass.d t1, f1|Classify a floating point number (64 bit)| +|fclass.s t1, f1|Classify a floating point number| +|fcvt.d.s t1, f1, dyn|Convert a float to a double: Assigned the value of f2 to f1| +|fcvt.d.w f1, t1, dyn|Convert double from integer: Assigns the value of t1 to f1| +|fcvt.d.wu f1, t1, dyn|Convert double from unsigned integer: Assigns the value of t1 to f1| +|fcvt.s.d t1, f1, dyn|Convert a double to a float: Assigned the value of f2 to f1| +|fcvt.s.w f1, t1, dyn|Convert float from integer: Assigns the value of t1 to f1| +|fcvt.s.wu f1, t1, dyn|Convert float from unsigned integer: Assigns the value of t1 to f1| +|fcvt.w.d t1, f1, dyn|Convert integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.w.s t1, f1, dyn|Convert integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.wu.d t1, f1, dyn|Convert unsinged integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.wu.s t1, f1, dyn|Convert unsinged integer from float: Assigns the value of f1 (rounded) to t1| +|fdiv.d f1, f2, f3, dyn|Floating DIVide (64 bit): assigns f1 to f2 / f3| +|fdiv.s f1, f2, f3, dyn|Floating DIVide: assigns f1 to f2 / f3| +|fence 1, 1|Ensure that IO and memory accesses before the fence happen before the following IO and memory accesses as viewed by a different thread| +|fence.i|Ensure that stores to instruction memory are visible to instruction fetches| +|feq.d t1, f1, f2|Floating EQuals (64 bit): if f1 = f2, set t1 to 1, else set t1 to 0| +|feq.s t1, f1, f2|Floating EQuals: if f1 = f2, set t1 to 1, else set t1 to 0| +|fld f1, -100(t1)|Load a double from memory| +|fle.d t1, f1, f2|Floating Less than or Equals (64 bit): if f1 <= f2, set t1 to 1, else set t1 to 0| +|fle.s t1, f1, f2|Floating Less than or Equals: if f1 <= f2, set t1 to 1, else set t1 to 0| +|flt.d t1, f1, f2|Floating Less Than (64 bit): if f1 < f2, set t1 to 1, else set t1 to 0| +|flt.s t1, f1, f2|Floating Less Than: if f1 < f2, set t1 to 1, else set t1 to 0| +|flw f1, -100(t1)|Load a float from memory| +|fmadd.d f1, f2, f3, f4, dyn|Fused Multiply Add (64 bit): Assigns f2*f3+f4 to f1| +|fmadd.s f1, f2, f3, f4, dyn|Fused Multiply Add: Assigns f2*f3+f4 to f1| +|fmax.d f1, f2, f3|Floating MAXimum (64 bit): assigns f1 to the larger of f1 and f3| +|fmax.s f1, f2, f3|Floating MAXimum: assigns f1 to the larger of f1 and f3| +|fmin.d f1, f2, f3|Floating MINimum (64 bit): assigns f1 to the smaller of f1 and f3| +|fmin.s f1, f2, f3|Floating MINimum: assigns f1 to the smaller of f1 and f3| +|fmsub.d f1, f2, f3, f4, dyn|Fused Multiply Subatract: Assigns f2*f3-f4 to f1| +|fmsub.s f1, f2, f3, f4, dyn|Fused Multiply Subatract: Assigns f2*f3-f4 to f1| +|fmul.d f1, f2, f3, dyn|Floating MULtiply (64 bit): assigns f1 to f2 * f3| +|fmul.s f1, f2, f3, dyn|Floating MULtiply: assigns f1 to f2 * f3| +|fmv.s.x f1, t1|Move float: move bits representing a float from an integer register| +|fmv.x.s t1, f1|Move float: move bits representing a float to an integer register| +|fnmadd.d f1, f2, f3, f4, dyn|Fused Negate Multiply Add (64 bit): Assigns -(f2*f3+f4) to f1| +|fnmadd.s f1, f2, f3, f4, dyn|Fused Negate Multiply Add: Assigns -(f2*f3+f4) to f1| +|fnmsub.d f1, f2, f3, f4, dyn|Fused Negated Multiply Subatract: Assigns -(f2*f3-f4) to f1| +|fnmsub.s f1, f2, f3, f4, dyn|Fused Negated Multiply Subatract: Assigns -(f2*f3-f4) to f1| +|fsd f1, -100(t1)|Store a double to memory| +|fsgnj.d f1, f2, f3|Floating point sign injection (64 bit): replace the sign bit of f2 with the sign bit of f3 and assign it to f1| +|fsgnj.s f1, f2, f3|Floating point sign injection: replace the sign bit of f2 with the sign bit of f3 and assign it to f1| +|fsgnjn.d f1, f2, f3|Floating point sign injection (inverted 64 bit): replace the sign bit of f2 with the opposite of sign bit of f3 and assign it to f1| +|fsgnjn.s f1, f2, f3|Floating point sign injection (inverted): replace the sign bit of f2 with the opposite of sign bit of f3 and assign it to f1| +|fsgnjx.d f1, f2, f3|Floating point sign injection (xor 64 bit): xor the sign bit of f2 with the sign bit of f3 and assign it to f1| +|fsgnjx.s f1, f2, f3|Floating point sign injection (xor): xor the sign bit of f2 with the sign bit of f3 and assign it to f1| +|fsqrt.d f1, f2, dyn|Floating SQuare RooT (64 bit): Assigns f1 to the square root of f2| +|fsqrt.s f1, f2, dyn|Floating SQuare RooT: Assigns f1 to the square root of f2| +|fsub.d f1, f2, f3, dyn|Floating SUBtract (64 bit): assigns f1 to f2 - f3| +|fsub.s f1, f2, f3, dyn|Floating SUBtract: assigns f1 to f2 - f3| +|fsw f1, -100(t1)|Store a float to memory| +|jal t1, target|Jump and link : Set t1 to Program Counter (return address) then jump to statement at target address| +|jalr t1, t2, -100|Jump and link register: Set t1 to Program Counter (return address) then jump to statement at t2 + immediate| +|lb t1, -100(t2)|Set t1 to sign-extended 8-bit value from effective memory byte address| +|lbu t1, -100(t2)|Set t1 to zero-extended 8-bit value from effective memory byte address| +|lh t1, -100(t2)|Set t1 to sign-extended 16-bit value from effective memory halfword address| +|lhu t1, -100(t2)|Set t1 to zero-extended 16-bit value from effective memory halfword address| +|lui t1,100000|Load upper immediate: set t1 to 20-bit followed by 12 0s| +|lw t1, -100(t2)|Set t1 to contents of effective memory word address| +|mul t1,t2,t3|Multiplication: set t1 to the lower 32 bits of t2*t3| +|mulh t1,t2,t3|Multiplication: set t1 to the upper 32 bits of t2*t3 using signed multiplication| +|mulhsu t1,t2,t3|Multiplication: set t1 to the upper 32 bits of t2*t3 where t2 is signed and %t3 is unsigned| +|mulhu t1,t2,t3|Multiplication: set t1 to the upper 32 bits of t2*t3 using unsigned multiplication| +|or t1,t2,t3|Bitwise OR : Set t1 to bitwise OR of t2 and t3| +|ori t1,t2,-100|Bitwise OR immediate : Set t1 to bitwise OR of t2 and sign-extended 12-bit immediate| +|rem t1,t2,t3|Remainder: set t1 to the remainder of t2/t3| +|remu t1,t2,t3|Remainder: set t1 to the remainder of t2/t3 using unsigned division| +|sb t1, -100(t2)|Store byte : Store the low-order 8 bits of t1 into the effective memory byte address| +|sh t1, -100(t2)|Store halfword : Store the low-order 16 bits of t1 into the effective memory halfword address| +|sll t1,t2,t3|Shift left logical: Set t1 to result of shifting t2 left by number of bits specified by value in low-order 5 bits of t3| +|slli t1,t2,10|Shift left logical : Set t1 to result of shifting t2 left by number of bits specified by immediate| +|slt t1,t2,t3|Set less than : If t2 is less than t3, then set t1 to 1 else set t1 to 0| +|slti t1,t2,-100|Set less than immediate : If t2 is less than sign-extended 12-bit immediate, then set t1 to 1 else set t1 to 0| +|sltiu t1,t2,-100|Set less than immediate unsigned : If t2 is less than sign-extended 16-bit immediate using unsigned comparison, then set t1 to 1 else set t1 to 0| +|sltu t1,t2,t3|Set less than : If t2 is less than t3 using unsigned comparision, then set t1 to 1 else set t1 to 0| +|sra t1,t2,t3|Shift right arithmetic: Set t1 to result of sign-extended shifting t2 right by number of bits specified by value in low-order 5 bits of t3| +|srai t1,t2,10|Shift right arithmetic : Set t1 to result of sign-extended shifting t2 right by number of bits specified by immediate| +|srl t1,t2,t3|Shift right logical: Set t1 to result of shifting t2 right by number of bits specified by value in low-order 5 bits of t3| +|srli t1,t2,10|Shift right logical : Set t1 to result of shifting t2 right by number of bits specified by immediate| +|sub t1,t2,t3|Subtraction: set t1 to (t2 minus t3)| +|sw t1, -100(t2)|Store word : Store contents of t1 into effective memory word address| +|uret|Return from handling an interrupt or exception (to uepc)| +|wfi|Wait for Interrupt| +|xor t1,t2,t3|Bitwise XOR : Set t1 to bitwise XOR of t2 and t3| +|xori t1,t2,-100|Bitwise XOR immediate : Set t1 to bitwise XOR of t2 and sign-extended 12-bit immediate| + +Supported psuedo-instructions: + +| Example Usage | Description | +|---------------|-------------| +|addi t1,t2,%lo(label) |Load Lower Address : Set t1 to t2 + lower 12-bit label's address| +|b label |Branch : Branch to statement at label unconditionally| +|beqz t1,label |Branch if EQual Zero : Branch to statement at label if t1 == 0| +|bgez t1,label |Branch if Greater than or Equal to Zero : Branch to statement at label if t1 >= 0| +|bgt t1,t2,label |Branch if Greater Than : Branch to statement at label if t1 > t2| +|bgtu t1,t2,label |Branch if Greater Than Unsigned: Branch to statement at label if t1 > t2 (unsigned compare)| +|bgtz t1,label |Branch if Greater Than: Branch to statement at label if t1 > 0| +|ble t1,t2,label |Branch if Less or Equal : Branch to statement at label if t1 <= t2| +|bleu t1,t2,label |Branch if Less or Equal Unsigned : Branch to statement at label if t1 <= t2 (unsigned compare)| +|blez t1,label |Branch if Less than or Equal to Zero : Branch to statement at label if t1 <= 0| +|bltz t1,label |Branch if Less Than Zero : Branch to statement at label if t1 < 0| +|bnez t1,label |Branch if Not Equal Zero : Branch to statement at label if t1 != 0| +|call label |CALL: call a far-away subroutine| +|csrc t1, fcsr |Clear bits in control and status register| +|csrci fcsr, 100 |Clear bits in control and status register| +|csrr t1, fcsr |Read control and status register| +|csrs t1, fcsr |Set bits in control and status register| +|csrsi fcsr, 100 |Set bits in control and status register| +|csrw t1, fcsr |Write control and status register| +|csrwi fcsr, 100 |Write control and status register| +|fabs.d f1, f2 | Set f1 to the absolute value of f2 (64 bit)| +|fabs.s f1, f2 | Set f1 to the absolute value of f2| +|fadd.d f1, f2, f3 |Floating ADD (64 bit): assigns f1 to f2 + f3| +|fadd.s f1, f2, f3 |Floating ADD: assigns f1 to f2 + f3| +|fcvt.d.s f1, f2 |Convert float to double: Assigned the value of f2 to f1| +|fcvt.d.w f1, t1 |Convert double from signed integer: Assigns the value of t1 to f1| +|fcvt.d.wu f1, t1 |Convert double from unsigned integer: Assigns the value of t1 to f1| +|fcvt.s.d f1, f2 |Convert double to float: Assigned the value of f2 to f1| +|fcvt.s.w f1, t1 |Convert float from signed integer: Assigns the value of t1 to f1| +|fcvt.s.wu f1, t1 |Convert float from unsigned integer: Assigns the value of t1 to f1| +|fcvt.w.d t1, f1 |Convert signed integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.w.s t1, f1 |Convert signed integer from float: Assigns the value of f1 (rounded) to t1| +|fcvt.wu.d t1, f1 |Convert unsigned integer from double: Assigns the value of f1 (rounded) to t1| +|fcvt.wu.s t1, f1 |Convert unsigned integer from float: Assigns the value of f1 (rounded) to t1| +|fdiv.d f1, f2, f3 |Floating DIVide (64 bit): assigns f1 to f2 / f3| +|fdiv.s f1, f2, f3 |Floating DIVide: assigns f1 to f2 / f3| +|fge.d t1, f2, f3 |Floating Greater Than or Equal (64 bit): if f1 >= f2, set t1 to 1, else set t1 to 0| +|fge.s t1, f2, f3 |Floating Greater Than or Equal: if f1 >= f2, set t1 to 1, else set t1 to 0| +|fgt.d t1, f2, f3 |Floating Greater Than (64 bit): if f1 > f2, set t1 to 1, else set t1 to 0| +|fgt.s t1, f2, f3 |Floating Greater Than: if f1 > f2, set t1 to 1, else set t1 to 0| +|fld f1,(t2) |Load Word: Set f1 to 64-bit value from effective memory word address| +|fld f1,-100 |Load Word: Set f1 to 64-bit value from effective memory word address| +|fld f1,10000000,t3|Load Word: Set f1 to 64-bit value from effective memory word address using t3 as a temporary| +|fld f1,label, t3 |Load Word: Set f1 to 64-bit value from effective memory word address using t3 as a temporary| +|flw f1,%lo(label)(t2) |Load from Address| +|flw f1,(t2) |Load Word Coprocessor 1 : Set f1 to 32-bit value from effective memory word address| +|flw f1,-100 |Load Word Coprocessor 1 : Set f1 to 32-bit value from effective memory word address| +|flw f1,10000000,t3|Load Word Coprocessor 1 : Set f1 to 32-bit value from effective memory word address using t3 as a temporary| +|flw f1,label, t3|Load Word Coprocessor 1 : Set f1 to 32-bit value from effective memory word address using t3 as a temporary| +|flwd f1,%lo(label)(t2) |Load from Address| +|fmadd.d f1, f2, f3, f4 |Fused Multiply Add (64 bit): Assigns f2*f3+f4 to f1| +|fmadd.s f1, f2, f3, f4 |Fused Multiply Add: Assigns f2*f3+f4 to f1| +|fmsub.d f1, f2, f3, f4 |Fused Multiply Subatract (64 bit): Assigns f2*f3-f4 to f1| +|fmsub.s f1, f2, f3, f4 |Fused Multiply Subatract: Assigns f2*f3-f4 to f1| +|fmul.d f1, f2, f3 |Floating MULtiply (64 bit): assigns f1 to f2 * f3| +|fmul.s f1, f2, f3 |Floating MULtiply: assigns f1 to f2 * f3| +|fmv.d f1, f2 | Move the value of f2 to f1 (64 bit)| +|fmv.s f1, f2 | Move the value of f2 to f1| +|fmv.w.x t1, f1 |Move float (New mnemonic): move bits representing a float from an integer register| +|fmv.x.w t1, f1 |Move float (New mnemonic): move bits representing a float to an integer register| +|fneg.d f1, f2 | Set f1 to the negation of f2 (64 bit)| +|fneg.s f1, f2 | Set f1 to the negation of f2| +|fnmadd.d f1, f2, f3, f4 |Fused Negate Multiply Add (64 bit): Assigns -(f2*f3+f4) to f1| +|fnmadd.s f1, f2, f3, f4 |Fused Negate Multiply Add: Assigns -(f2*f3+f4) to f1| +|fnmsub.d f1, f2, f3, f4 |Fused Negated Multiply Subatract (64 bit): Assigns -(f2*f3-f4) to f1| +|fnmsub.s f1, f2, f3, f4 |Fused Negated Multiply Subatract: Assigns -(f2*f3-f4) to f1| +|frcsr t1 |Read FP control/status register| +|frflags t1 |Read FP exception flags| +|frrm t1 |Read FP rounding mode| +|frsr t1 |Alias for frcsr t1| +|fscsr t1 |Write FP control/status register| +|fscsr t1, t2 |Swap FP control/status register| +|fsd f1,(t2) |Store Word: Store 64-bit value from f1 to effective memory word address| +|fsd f1,-100 |Store Word: Store 64-bit value from f1 to effective memory word address| +|fsd f1,10000000,t3|Store Word: Store 64-bit value from f1 to effective memory word address using t3 as a temporary| +|fsd f1,label, t3 |Store Word: Store 64-bit value from f1 to effective memory word address using t3 as a temporary| +|fsflags t1 |Write FP exception flags| +|fsflags t1, t2 |Swap FP exception flags| +|fsflagsi 100 |Write FP exception flags, immediate| +|fsflagsi t1, 100 |Swap FP exception flags, immediate| +|fsqrt.d f1, f2 |Floating SQuare RooT (64 bit): Assigns f1 to the square root of f2| +|fsqrt.s f1, f2 |Floating SQuare RooT: Assigns f1 to the square root of f2| +|fsrm t1 |Write FP rounding mode| +|fsrm t1, t2 |Swap FP rounding mode| +|fsrmi 100 |Write FP rounding mode, immediate| +|fsrmi t1, 100 |Swap FP rounding mode, immediate| +|fssr t1 |Alias for fscsr t1 | +|fssr t1, t2 |Alias for fscsr t1, t2| +|fsub.d f1, f2, f3 |Floating SUBtract (64 bit): assigns f1 to f2 - f3| +|fsub.s f1, f2, f3 |Floating SUBtract: assigns f1 to f2 - f3| +|fsw f1,(t2) |Store Word Coprocessor 1 : Store 32-bit value from f1 to effective memory word address| +|fsw f1,-100 |Store Word Coprocessor 1 : Store 32-bit value from f1 to effective memory word address| +|fsw f1,10000000,t3|Store Word Coprocessor 1 : Store 32-bit value from f1 to effective memory word address using t3 as a temporary| +|fsw f1,label, t3 |Store Word Coprocessor 1 : Store 32-bit value from f1 to effective memory word address using t3 as a temporary| +|j label |Jump : Jump to statement at label| +|jal label |Jump And Link: Jump to statement at label and set the return address to ra| +|jalr t0 |Jump And Link Register: Jump to address in t0 and set the return address to ra| +|jalr t0, -100 |Jump And Link Register: Jump to address in t0 and set the return address to ra| +|jr t0 |Jump Register: Jump to address in t0| +|jr t0, -100 |Jump Register: Jump to address in t0| +|la t1,label |Load Address : Set t1 to label's address| +|lb t1,(t2) |Load Byte : Set t1 to sign-extended 8-bit value from effective memory byte address| +|lb t1,-100 |Load Byte : Set $1 to sign-extended 8-bit value from effective memory byte address| +|lb t1,10000000 |Load Byte : Set $t1 to sign-extended 8-bit value from effective memory byte address| +|lb t1,label |Load Byte : Set $t1 to sign-extended 8-bit value from effective memory byte address| +|lbu t1,(t2) |Load Byte Unsigned : Set $t1 to zero-extended 8-bit value from effective memory byte address| +|lbu t1,-100 |Load Byte Unsigned : Set $t1 to zero-extended 8-bit value from effective memory byte address| +|lbu t1,10000000 |Load Byte Unsigned : Set t1 to zero-extended 8-bit value from effective memory byte address| +|lbu t1,label |Load Byte Unsigned : Set t1 to zero-extended 8-bit value from effective memory byte address| +|lh t1,(t2) |Load Halfword : Set t1 to sign-extended 16-bit value from effective memory halfword address| +|lh t1,-100 |Load Halfword : Set t1 to sign-extended 16-bit value from effective memory halfword address| +|lh t1,10000000 |Load Halfword : Set t1 to sign-extended 16-bit value from effective memory halfword address| +|lh t1,label |Load Halfword : Set t1 to sign-extended 16-bit value from effective memory halfword address| +|lhu t1,(t2) |Load Halfword Unsigned : Set t1 to zero-extended 16-bit value from effective memory halfword address| +|lhu t1,-100 |Load Halfword Unsigned : Set t1 to zero-extended 16-bit value from effective memory halfword address| +|lhu t1,10000000 |Load Halfword Unsigned : Set t1 to zero-extended 16-bit value from effective memory halfword address| +|lhu t1,label |Load Halfword Unsigned : Set t1 to zero-extended 16-bit value from effective memory halfword address| +|li t1,-100 |Load Immediate : Set t1 to 12-bit immediate (sign-extended)| +|li t1,10000000 |Load Immediate : Set t1 to 32-bit immediate| +|lui t1,%hi(label) |Load Upper Address : Set t1 to upper 20-bit label's address| +|lw t1,%lo(label)(t2) |Load from Address| +|lw t1,(t2) |Load Word : Set t1 to contents of effective memory word address| +|lw t1,-100 |Load Word : Set t1 to contents of effective memory word address| +|lw t1,10000000 |Load Word : Set t1 to contents of effective memory word address| +|lw t1,label |Load Word : Set t1 to contents of memory word at label's address| +|mv t1,t2 |MoVe : Set t1 to contents of t2| +|neg t1,t2 |NEGate : Set t1 to negation of t2| +|nop |NO OPeration| +|not t1,t2 |Bitwise NOT (bit inversion)| +|rdcycle t1 | Read from cycle| +|rdcycleh t1 | Read from cycleh| +|rdinstret t1 | Read from instret| +|rdinstreth t1 | Read from instreth| +|rdtime t1 | Read from time| +|rdtimeh t1 | Read from timeh| +|ret |Return: return from a subroutine| +|sb t1,(t2) |Store Byte : Store the low-order 8 bits of t1 into the effective memory byte address| +|sb t1,-100 |Store Byte : Store the low-order 8 bits of $t1 into the effective memory byte address| +|sb t1,10000000,t2 |Store Byte : Store the low-order 8 bits of $t1 into the effective memory byte address| +|sb t1,label,t2 |Store Byte : Store the low-order 8 bits of $t1 into the effective memory byte address| +|seqz t1,t2 |Set EQual to Zero : if t2 == 0 then set t1 to 1 else 0| +|sgt t1,t2,t3 |Set Greater Than : if t2 greater than t3 then set t1 to 1 else 0| +|sgtu t1,t2,t3 |Set Greater Than Unsigned : if t2 greater than t3 (unsigned compare) then set t1 to 1 else 0| +|sgtz t1,t2 |Set Greater Than Zero : if t2 > 0 then set t1 to 1 else 0| +|sh t1,(t2) |Store Halfword : Store the low-order 16 bits of $1 into the effective memory halfword address| +|sh t1,-100 |Store Halfword : Store the low-order 16 bits of $t1 into the effective memory halfword address| +|sh t1,10000000,t2 |Store Halfword : Store the low-order 16 bits of t1 into the effective memory halfword address using t2 as a temporary| +|sh t1,label,t2 |Store Halfword : Store the low-order 16 bits of t1 into the effective memory halfword address using t2 as a temporary| +|sltz t1,t2 |Set Less Than Zero : if t2 < 0 then set t1 to 1 else 0| +|snez t1,t2 |Set Not Equal to Zero : if t2 != 0 then set t1 to 1 else 0| +|sw t1,(t2) |Store Word : Store t1 contents into effective memory word address| +|sw t1,-100 |Store Word : Store $t1 contents into effective memory word address| +|sw t1,10000000,t2 |Store Word : Store $t1 contents into effective memory word address using t2 as a temporary| +|sw t1,label,t2 |Store Word : Store $t1 contents into memory word at label's address using t2 as a temporary| +|tail label |TAIL call: tail call (call without saving return address)a far-away subroutine| + From 3139a0f226006d6458ed14550b90bfb48a2c1f6b Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Mon, 3 Aug 2020 19:40:57 +0800 Subject: [PATCH 13/43] add bnf of c syntax --- doc/C-syntax-in-bnf.md | 236 +++++++++++++++++++++++++++++++++++++++++ doc/bnf-intro.md | 50 +++++++++ 2 files changed, 286 insertions(+) create mode 100644 doc/C-syntax-in-bnf.md create mode 100644 doc/bnf-intro.md diff --git a/doc/C-syntax-in-bnf.md b/doc/C-syntax-in-bnf.md new file mode 100644 index 0000000..30d3739 --- /dev/null +++ b/doc/C-syntax-in-bnf.md @@ -0,0 +1,236 @@ +# The syntax of C in Backus-Naur Form + ::= {}* + + ::= + | + + ::= {}* {}* + + ::= + | + | + + ::= auto + | register + | static + | extern + | typedef + + ::= void + | char + | short + | int + | long + | float + | double + | signed + | unsigned + | + | + | + + ::= { {}+ } + | { {}+ } + | + + ::= struct + | union + + ::= {}* + + ::= + | + + ::= + | , + + ::= + | : + | : + + ::= {}? + + ::= * {}* {}? + + ::= const + | volatile + + ::= + | ( ) + | [ {}? ] + | ( ) + | ( {}* ) + + ::= + + ::= + | ? : + + ::= + | || + + ::= + | && + + ::= + | | + + ::= + | ^ + + ::= + | & + + ::= + | == + | != + + ::= + | < + | > + | <= + | >= + + ::= + | << + | >> + + ::= + | + + | - + + ::= + | * + | / + | % + + ::= + | ( ) + + ::= + | ++ + | -- + | + | sizeof + | sizeof + + ::= + | [ ] + | ( {}* ) + | . + | -> + | ++ + | -- + + ::= + | + | + | ( ) + + ::= + | + | + | + + ::= + | , + + ::= + | + + ::= = + | *= + | /= + | %= + | += + | -= + | <<= + | >>= + | &= + | ^= + | |= + + ::= & + | * + | + + | - + | ~ + | ! + + ::= {}+ {}? + + ::= + | , ... + + ::= + | , + + ::= {}+ + | {}+ + | {}+ + + ::= + | + | + + ::= ( ) + | {}? [ {}? ] + | {}? ( {}? ) + + ::= enum { } + | enum { } + | enum + + ::= + | , + + ::= + | = + + ::= + + ::= {}+ {}* ; + + ::= + | = + + ::= + | { } + | { , } + + ::= + | , + + ::= { {}* {}* } + + ::= + | + | + | + | + | + + ::= : + | case : + | default : + + ::= {}? ; + + ::= if ( ) + | if ( ) else + | switch ( ) + + ::= while ( ) + | do while ( ) ; + | for ( {}? ; {}? ; {}? ) + + ::= goto ; + | continue ; + | break ; + | return {}? ; + +This grammar was adapted from Section A13 of The C programming language, 2nd edition, by Brian W. Kernighan and Dennis M. Ritchie,Prentice Hall, 1988. + +## references +- https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm +- http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf diff --git a/doc/bnf-intro.md b/doc/bnf-intro.md new file mode 100644 index 0000000..6f685a9 --- /dev/null +++ b/doc/bnf-intro.md @@ -0,0 +1,50 @@ +BNF（Backus-Naur Form）是John Backus 在20世纪90年代提出的用以简洁描述一种编程语言的语言，后经过和 Peter Naur进行改进，简称 BNF 范式，是一种用递归的思想来表述计算机语言符号集的定义规范，基本结构为： + +``` + ::= +``` +法则： +``` +::=表示定义； +“ ”双引号里的内容表示字符； +在双引号中的字("word")代表着这些字符本身。而double_quote用来代表双引号； +在双引号外的字（有可能有下划线）代表着语法部分； +尖括号( < > )内包含的为必选项； +方括号( [ ] )内包含的为可选项； +大括号( { } )内包含的为可重复0至无数次的项； +竖线( | )表示在其左右两边任选一项，相当于"OR"的意思。 +``` + +> Extended BNF ，允许使用循环，但正真的BNF只需要递归就够了。下面是EBNF的要点： +> +> ``` +> "..." : 术语符号 +> [...] : 选项:最多出现一次 +> {...} : 重复项: 任意次数，包括 0 次 +> (...) : 分组 +> | : 并列选项，只能选一个 +> 斜体字: 参数，在其它地方有解释 +> ``` +> +> + +例如，四则运算的规则可以表示如下： + +``` + ::= + + | - + | + + ::= * + | / + | + + ::= ( ) + | Num +``` + +用尖括号 `<>` 括起来的就称作 **非终结符** ，因为它们可以用 `::=` 右侧的式子代替。`|` 表示选择，如 `` 可以是 ` + `、` - `或 `` 中的一种。而没有出现在`::=`左边的就称作 **终结符** ，一般终结符对应于词法分析器输出的标记（token）。 + +``` + +``` \ No newline at end of file From 4ce3f841d3e63ac385cf728ea2ca7888e7b1a230 Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Mon, 3 Aug 2020 21:02:59 +0800 Subject: [PATCH 14/43] add second choice of minidecaf spec --- doc/minidecaf-spec.md | 795 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 794 insertions(+), 1 deletion(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index cc40b2e..b0471ae 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -1,4 +1,7 @@ +# 第一种选择 +缺点：step1-10的input还不是正常的C程序 + - * means the preceding element is repeated zero or more times - + means one or more repeats - ? means optional(zero or one) @@ -251,5 +254,795 @@ primary = num typ = ("int" | "char") "*"* ``` -## feature文法 + +# 第二种选择 + +特点：每个步骤的input都是一个正常的C程序，可以用于所写编译器的编译出的目标程序的运行结果与gcc等正常编译器的编译出的目标程序的运行结果进行直接比较 + +还缺 指针，数组，string等相关的spec + +## 步骤1：Integers +只有正整数，大致形式是 `0` 或 `5`，语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" "}" +< ::= "return" ";" | "int" "=" ";" + ::= +``` + +例子： +``` +int main() { + return 2; +} +``` + +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis \( +Close parenthesis \) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +``` +对应的AST为： +``` +program = Program(function_declaration) +function_declaration = Function(string, statement) //string is the function name +statement = Return(exp) | Assign(variable, exp) +exp = Constant(int) +``` + +## 步骤2：Unary Operators +有"- ~ !"操作，语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" "}" + ::= "return" ";" + ::= | + ::= "!" | "~" | "-" +``` + +例子： +``` +int main() { + return -2; +} +``` + +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis \( +Close parenthesis \) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Negation - +Bitwise complement ~ +Logical negation ! +``` + +对应的AST为： +``` +program = Program(function_declaration) +function_declaration = Function(string, statement) //string is the function name +statement = Return(exp) +exp = UnOp(operator, exp) | Constant(int) + +``` + +## 步骤3：Binary Operators +支持 +``` +Addition + +Subtraction - +Multiplication * +Division / +``` + +语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" "}" + ::= "return" ";" + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | +``` + +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis ( +Close parenthesis ) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Minus - +Bitwise complement ~ +Logical negation ! +Addition + +Multiplication * +Division / +``` + +对应的AST为： +``` +program = Program(function_declaration) +function_declaration = Function(string, statement) //string is the function name +statement = Return(exp) +exp = BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) +``` + +## 步骤4：Logical Binary Operators +支持 +``` +Logical AND && +Logical OR || +Equal to == +Not equal to != +Less than < +Less than or equal to <= +Greater than > +Greater than or equal to >= +``` +语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" "}" + ::= "return" ";" + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | + ::= "!" | "~" | "-" +``` +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis ( +Close parenthesis ) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Minus - +Bitwise complement ~ +Logical negation ! +Addition + +Multiplication * +Division / +AND && +OR || +Equal == +Not Equal != +Less than < +Less than or equal <= +Greater than > +Greater than or equal >= +``` +对应的AST为： +``` +program = Program(function_declaration) +function_declaration = Function(string, statement) //string is the function name +statement = Return(exp) +exp = BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) +``` + +## 步骤5：Local Variables +支持Local Variables +``` +int a; +a=3; +... +``` +语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" { } "}" + ::= "return" ";" + | ";" + | "int" [ = ] ";" + ::= "=" | + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | | + ::= "!" | "~" | "-" +``` +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis ( +Close parenthesis ) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Minus - +Bitwise complement ~ +Logical negation ! +Addition + +Multiplication * +Division / +AND && +OR || +Equal == +Not Equal != +Less than < +Less than or equal <= +Greater than > +Greater than or equal >= +Assignment = +``` + +对应的AST为： +``` +program = Program(function_declaration) +function_declaration = Function(string, statement list) //string is the function name +statement = Return(exp) + | Declare(string, exp option) //string is variable name + //exp is optional initializer + | Exp(exp) +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) +``` + +## 步骤6：Conditional statements & expressions +例如 +``` +if (flag) { + int e = a ? b : c; + return a*2; +} +``` +，语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" { } "}" + ::= | + ::= "int" [ = ] ";" + ::= "return" ";" + | ";" + | "if" "(" ")" [ "else" ] + + + ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | | + ::= "!" | "~" | "-" +``` +对应的Token为： +``` +Open brace { +Close brace } +Open parenthesis ( +Close parenthesis ) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Minus - +Bitwise complement ~ +Logical negation ! +Addition + +Multiplication * +Division / +AND && +OR || +Equal == +Not Equal != +Less than < +Less than or equal <= +Greater than > +Greater than or equal >= +Assignment = +If keyword if +Else keyword else +Colon : +Question mark ? +``` +对应的AST为： +``` +program = Program(function_declaration) + +function_declaration = Function(string, block_item list) //string is the function name + +block_item = Statement(statement) | Declaration(declaration) + +declaration = Declare(string, exp option) //string is variable name + //exp is optional initializer + +statement = Return(exp) + | Exp(exp) + | Conditional(exp, statement, statement option) //exp is controlling condition + //first statement is 'if' block + //second statement is optional 'else' block + +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) + | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively +``` + +## 步骤7：Compound Statements +例如 +``` +int main() { + int a; + { + //this is also a compound statement! + a = 4; + } +} +``` +语言语法为： + +``` + ::= + ::= "int" "(" ")" "{" { } "}" + ::= | + ::= "int" [ = ] ";" + ::= "return" ";" + | ";" + | "if" "(" ")" [ "else" ] + | "{" { } "} + ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | | + ::= "!" | "~" | "-" +``` +对应的Token为（不变）： +``` +Open brace { +Close brace } +Open parenthesis ( +Close parenthesis ) +Semicolon ; +Int keyword int +Return keyword return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +Minus - +Bitwise complement ~ +Logical negation ! +Addition + +Multiplication * +Division / +AND && +OR || +Equal == +Not Equal != +Less than < +Less than or equal <= +Greater than > +Greater than or equal >= +Assignment = +If keyword if +Else keyword else +Colon : +Question mark ? +``` +对应的AST为： +``` +program = Program(function_declaration) + +function_declaration = Function(string, block_item list) //string is the function name + +block_item = Statement(statement) | Declaration(declaration) + +declaration = Declare(string, exp option) //string is variable name + //exp is optional initializer + +statement = Return(exp) + | Exp(exp) + | Conditional(exp, statement, statement option) //exp is controlling condition + //first statement is 'if' block + //second statement is optional 'else' block + | Compound(block_item list) + +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) + | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively +``` + +## 步骤8：Loops +例如 +``` +int i; +for (i = 0; i < 10; i = i + 1) { + //do something +} + +while (i < 10) { + i = i + 1; +} +``` +语言语法为：(注意语法和AST定义之间存在差异;语法允许for循环中的控制表达式为空，但AST不允许。) + +``` + ::= + ::= "int" "(" ")" "{" { } "}" + ::= | + ::= "int" [ = ] ";" + ::= "return" ";" + | // null statement + | "if" "(" ")" [ "else" ] + | "{" { } "} + | "for" "(" ")" + | "for" "(" ")" + | "while" "(" ")" + | "do" "while" ";" + | "break" ";" + | "continue" ";" + ::= ";" | ";" + ::= ")" | ")" + ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= "(" ")" | | | + ::= "!" | "~" | "-" +``` +对应的Token为： +``` +{ +} +( +) +; +int +return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +- +~ +! ++ +* +/ +&& +|| +== +!= +< +<= +> +>= += +if +else +: +? +for +while +do +break +continue +``` +对应的AST为： +``` +program = Program(function_declaration) + +function_declaration = Function(string, block_item list) //string is the function name + +block_item = Statement(statement) | Declaration(declaration) + +declaration = Declare(string, exp option) //string is variable name + //exp is optional initializer + +statement = Return(exp) + | Exp(exp option) + | Conditional(exp, statement, statement option) // exp is controlling condition + // first statement is 'if' block + // second statement is optional 'else' block + | Compound(block_item list) + | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | While(expression, statement) // condition, body + | Do(statement, expression) // body, condition + | Break + | Continue + +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) + | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively +``` +## 步骤9：Functions +例如 +``` +int three() { + return 3; +} + +int main() { + return three(); +} +``` +语言语法为： + +``` + ::= { } + ::= "int" "(" [ "int" { "," "int" } ] ")" ( "{" { } "}" | ";" ) + ::= | + ::= "int" [ = ] ";" + ::= "return" ";" + | // null statement + | "if" "(" ")" [ "else" ] + | "{" { } "} + | "for" "(" ")" + | "for" "(" ")" + | "while" "(" ")" + | "do" "while" ";" + | "break" ";" + | "continue" ";" + ::= ";" | ";" + ::= ")" | ")" + ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= | "(" ")" | | | + ::= id "(" [ { "," } ] ")" + ::= "!" | "~" | "-" +``` +对应的Token为： +``` +{ +} +( +) +; +int +return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +- +~ +! ++ +* +/ +&& +|| +== +!= +< +<= +> +>= += +if +else +: +? +for +while +do +break +continue +, +``` +对应的AST为： +``` +program = Program(function_declaration list) + +function_declaration = Function(string, block_item list) //string is the function name + +block_item = Statement(statement) | Declaration(declaration) + +declaration = Declare(string, exp option) //string is variable name + //exp is optional initializer + +statement = Return(exp) + | Exp(exp option) + | Conditional(exp, statement, statement option) // exp is controlling condition + // first statement is 'if' block + // second statement is optional 'else' block + | Compound(block_item list) + | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | While(expression, statement) // condition, body + | Do(statement, expression) // body, condition + | Break + | Continue + +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) + | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively + | FunCall(string, exp list) // string is the function name +``` + +## 步骤10：Global Variables +例如 +``` +int foo; + +int fun1() { + foo = 3; + return 0; +} + +int fun2() { + return foo; +} + +int main() { + fun1(); + return fun2(); +} +``` +语言语法为： + +``` + ::= { | } + ::= "int" "(" [ "int" { "," "int" } ] ")" ( "{" { } "}" | ";" ) + ::= | + ::= "int" [ = ] ";" + ::= "return" ";" + | // null statement + | "if" "(" ")" [ "else" ] + | "{" { } "} + | "for" "(" ")" + | "for" "(" ")" + | "while" "(" ")" + | "do" "while" ";" + | "break" ";" + | "continue" ";" + ::= ";" | ";" + ::= ")" | ")" + ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/") } + ::= | "(" ")" | | | + ::= id "(" [ { "," } ] ")" + ::= "!" | "~" | "-" +``` + +对应的Token为(不变)： +``` +{ +} +( +) +; +int +return +Identifier [a-zA-Z]\w* +Integer literal [0-9]+ +- +~ +! ++ +* +/ +&& +|| +== +!= +< +<= +> +>= += +if +else +: +? +for +while +do +break +continue +, +``` +对应的AST为： +``` +toplevel_item = Function(function_declaration) + | Variable(declaration) +toplevel = Program(toplevel_item list) +program = Program(function_declaration list) + +function_declaration = Function(string, block_item list) //string is the function name + +block_item = Statement(statement) | Declaration(declaration) + +declaration = Declare(string, exp option) //string is variable name + //exp is optional initializer + +statement = Return(exp) + | Exp(exp option) + | Conditional(exp, statement, statement option) // exp is controlling condition + // first statement is 'if' block + // second statement is optional 'else' block + | Compound(block_item list) + | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | While(expression, statement) // condition, body + | Do(statement, expression) // body, condition + | Break + | Continue + +exp = Assign(string, exp) + | Var(string) //string is variable name + | BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) + | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively + | FunCall(string, exp list) // string is the function name +``` + + +# feature文法 小 feature 如 ternary expr ; var 以外加上 val ; 允许 var 做类型推断。 From 2fbacb17e26f7fd871546548b49218e000b297ec Mon Sep 17 00:00:00 2001 From: Yu Chen Date: Tue, 11 Aug 2020 11:27:30 +0800 Subject: [PATCH 15/43] little fix on minidecaf-spec.md --- doc/minidecaf-spec.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index b0471ae..f4d1fb2 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -338,10 +338,9 @@ program = Program(function_declaration) function_declaration = Function(string, statement) //string is the function name statement = Return(exp) exp = UnOp(operator, exp) | Constant(int) - ``` -## 步骤3：Binary Operators +## 步骤3：Binary Operators and Parenthesis for ( expr ) 支持 ``` Addition + @@ -359,6 +358,7 @@ Division / ::= { ("+" | "-") } ::= { ("*" | "/") } ::= "(" ")" | | + ::= "!" | "~" | "-" ``` 对应的Token为： From c4612aab01c6728675eaf7782287d20623752885 Mon Sep 17 00:00:00 2001 From: Hoblovski Date: Tue, 11 Aug 2020 22:06:35 +0800 Subject: [PATCH 16/43] ptr & arr proposal --- doc/minidecaf-spec.md | 170 ++++++++++++++++++++++++++++++++++-------- 1 file changed, 138 insertions(+), 32 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index f4d1fb2..39da178 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -116,7 +116,7 @@ stmt = expr ";" | "return" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? | "while" "(" expr ")" stmt - | "for" "(" expr? ";" expr? ";" expr? ")" stmt + | "for" "(" expr? ";" expr? ";" expr? ")" stmt expr = assign assign = equality ("=" assign)? equality = relational ("==" relational | "!=" relational)* @@ -139,7 +139,7 @@ stmt = expr ";" | "if" "(" expr ")" stmt ("else" stmt)? | "while" "(" expr ")" stmt | "for" "(" expr? ";" expr? ";" expr? ")" stmt - | "{" stmt* "}" + | "{" stmt* "}" expr = assign assign = equality ("=" assign)? equality = relational ("==" relational | "!=" relational)* @@ -160,7 +160,7 @@ stmt = expr ";" | "if" "(" expr ")" stmt ("else" stmt)? | "while" "(" expr ")" stmt | "for" "(" expr? ";" expr? ";" expr? ")" stmt - | "{" stmt* "}" + | "{" stmt* "}" expr = assign assign = equality ("=" assign)? equality = relational ("==" relational | "!=" relational)* @@ -168,7 +168,7 @@ relational = add ("<" add | "<=" add | ">" add | ">=" add)* add = mul ("+" mul | "-" mul)* mul = unary ("*" unary | "/" unary)* unary = ("+" | "-")? primary -primary = num +primary = num | ident ("(" ")")? | "(" expr ")" num = digit+ @@ -295,7 +295,7 @@ Integer literal [0-9]+ program = Program(function_declaration) function_declaration = Function(string, statement) //string is the function name statement = Return(exp) | Assign(variable, exp) -exp = Constant(int) +exp = Constant(int) ``` ## 步骤2：Unary Operators @@ -341,7 +341,7 @@ exp = UnOp(operator, exp) | Constant(int) ``` ## 步骤3：Binary Operators and Parenthesis for ( expr ) -支持 +支持 ``` Addition + Subtraction - @@ -415,7 +415,7 @@ Greater than or equal to >= ::= { ("+" | "-") } ::= { ("*" | "/") } ::= "(" ")" | | - ::= "!" | "~" | "-" + ::= "!" | "~" | "-" ``` 对应的Token为： ``` @@ -467,16 +467,16 @@ a=3; ::= "int" "(" ")" "{" { } "}" ::= "return" ";" | ";" - | "int" [ = ] ";" + | "int" [ = ] ";" ::= "=" | - ::= { "||" } + ::= { "||" } ::= { "&&" } ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } ::= "(" ")" | | | - ::= "!" | "~" | "-" + ::= "!" | "~" | "-" ``` 对应的Token为： ``` @@ -510,7 +510,7 @@ Assignment = ``` program = Program(function_declaration) function_declaration = Function(string, statement list) //string is the function name -statement = Return(exp) +statement = Return(exp) | Declare(string, exp option) //string is variable name //exp is optional initializer | Exp(exp) @@ -518,7 +518,7 @@ exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) | UnOp(unary_operator, exp) - | Constant(int) + | Constant(int) ``` ## 步骤6：Conditional statements & expressions @@ -591,15 +591,15 @@ function_declaration = Function(string, block_item list) //string is the functio block_item = Statement(statement) | Declaration(declaration) -declaration = Declare(string, exp option) //string is variable name +declaration = Declare(string, exp option) //string is variable name //exp is optional initializer -statement = Return(exp) +statement = Return(exp) | Exp(exp) | Conditional(exp, statement, statement option) //exp is controlling condition //first statement is 'if' block //second statement is optional 'else' block - + exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) @@ -680,16 +680,16 @@ function_declaration = Function(string, block_item list) //string is the functio block_item = Statement(statement) | Declaration(declaration) -declaration = Declare(string, exp option) //string is variable name +declaration = Declare(string, exp option) //string is variable name //exp is optional initializer -statement = Return(exp) +statement = Return(exp) | Exp(exp) | Conditional(exp, statement, statement option) //exp is controlling condition //first statement is 'if' block //second statement is optional 'else' block | Compound(block_item list) - + exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) @@ -728,7 +728,7 @@ while (i < 10) { | "break" ";" | "continue" ";" ::= ";" | ";" - ::= ")" | ")" + ::= ")" | ")" ::= "=" | ::= [ "?" ":" ] ::= { "||" } @@ -784,10 +784,10 @@ function_declaration = Function(string, block_item list) //string is the functio block_item = Statement(statement) | Declaration(declaration) -declaration = Declare(string, exp option) //string is variable name +declaration = Declare(string, exp option) //string is variable name //exp is optional initializer -statement = Return(exp) +statement = Return(exp) | Exp(exp option) | Conditional(exp, statement, statement option) // exp is controlling condition // first statement is 'if' block @@ -799,7 +799,7 @@ statement = Return(exp) | Do(statement, expression) // body, condition | Break | Continue - + exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) @@ -836,7 +836,7 @@ int main() { | "break" ";" | "continue" ";" ::= ";" | ";" - ::= ")" | ")" + ::= ")" | ")" ::= "=" | ::= [ "?" ":" ] ::= { "||" } @@ -894,10 +894,10 @@ function_declaration = Function(string, block_item list) //string is the functio block_item = Statement(statement) | Declaration(declaration) -declaration = Declare(string, exp option) //string is variable name +declaration = Declare(string, exp option) //string is variable name //exp is optional initializer -statement = Return(exp) +statement = Return(exp) | Exp(exp option) | Conditional(exp, statement, statement option) // exp is controlling condition // first statement is 'if' block @@ -909,7 +909,7 @@ statement = Return(exp) | Do(statement, expression) // body, condition | Break | Continue - + exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) @@ -955,8 +955,8 @@ int main() { | "do" "while" ";" | "break" ";" | "continue" ";" - ::= ";" | ";" - ::= ")" | ")" + ::= ";" | ";" + ::= ")" | ")" ::= "=" | ::= [ "?" ":" ] ::= { "||" } @@ -1011,17 +1011,17 @@ continue ``` toplevel_item = Function(function_declaration) | Variable(declaration) -toplevel = Program(toplevel_item list) +toplevel = Program(toplevel_item list) program = Program(function_declaration list) function_declaration = Function(string, block_item list) //string is the function name block_item = Statement(statement) | Declaration(declaration) -declaration = Declare(string, exp option) //string is variable name +declaration = Declare(string, exp option) //string is variable name //exp is optional initializer -statement = Return(exp) +statement = Return(exp) | Exp(exp option) | Conditional(exp, statement, statement option) // exp is controlling condition // first statement is 'if' block @@ -1033,7 +1033,7 @@ statement = Return(exp) | Do(statement, expression) // body, condition | Break | Continue - + exp = Assign(string, exp) | Var(string) //string is variable name | BinOp(binary_operator, exp, exp) @@ -1043,6 +1043,112 @@ exp = Assign(string, exp) | FunCall(string, exp list) // string is the function name ``` +## 步骤11 (WIP) 指针 + +指针和数组是否要做？ + +请完善 + +主要改动部分 + +``` +func + : ty Ident '(' paramList ')' (block | ';') // 参数本质就是 decl + ; + +ty + : 'int' + | ty '*' + ; + +decl + : ty Ident ('=' expr)? // 去掉了分号，之前用到的地方记得加分号 + ; + +paramList + : (decl (',' decl)*)? // 逗号隔开的 decl，并且语义检查 decl 不能有初始值 + ; + +factor + : ... + | '&' factor // 要做类型和 lvalue 检查，不允许 &(2+3) 这种 + // lvalue : Ident | '*' expr + | '*' factor // 要做类型检查 + ; +``` + +其中取地址算符 `&` 要求 +* 如果 `& Ident` 那直接返回 Ident 地址 +* `&*expr` 等价于 `expr`，（但是不再是 lvalue 了） + +## 步骤12 (WIP) 数组 + +请完善 + +主要改动部分 + +``` +decl + : ty Ident ('[' Integer ']')* ('=' expr)? // 语义检查：数组 decl 不能给初始值 + ; + +factor + : ... + | '&' factor // lvalue : Ident | '*' expr | expr '[' expr ']' + | expr '[' expr ']' // 要做类型检查，要求第一个 expr 类型是 ty* 或者数组 + // a: int[2][3]，那么 a[1]: int[3]，a[1][2]: int + // b: int*[2], 那么 b[1]: int*, b[1][3]: int +``` + +并且： +* 没有变长数组 `int a[n];` 也没有不定长数组 `int a[];` + - 否则预留空间和计算偏移量更麻烦——可以作为较复杂的小练习 +* 没有越界检查，有负长度检查 +* 指针不能指向数组，不存在 `int (*)[2]` 这种东西 + - 否则声明会很麻烦，如 `int (*a)[2]` 和 `int *a[2]` +* 数组初始化只能是默认零初始化，没字面量也不能 `int a[2] = {2, 3}` + - 否则麻烦 +* 数组可以在栈上或者 .bss（全局变量）里 +* 如果数组作为函数参数出现，不预留空间，否则预留空间并且零初始化 + +关于数组和指针的隐式转换 +* 只有一个地方允许指针和数组之间的隐式转换：传参，其他地方只能有数组到指针的显式类型转换 +* 如果形参类型是数组（如 `int* param[2][3]`），那么实参必须是同样的数组（`int *arg[2][3]`），或者同样基类型的指针（`int **arg`） +* 如果形参类型是指针（如 `int *param`），那么实参必须是同样的指针（`int *arg`），或者同样基类型的数组（`int arg[2]` 或 `int arg[3][10]`） + +例子： +``` +int a[2][2]; int b[3][3]; int c[2][2]; +int *p; int *q; + +void matmul2(int a[2][2], int b[2][2], int c[2][2]); // ok +matmul2(a, a, c); // ok +matmul2(a, b, c); // bad 长度不匹配 +p = (int*) b; q = (int*) c; matmul2(a, p, q); // ok，有两个 int* -> int[2][2] 的隐式转换 + +int *row2 = a[1]; // ok +row2 = a[1]; // bad，这里 int[2] -> int* 转换必须显式 + +a = p; // bad，数组不能赋值 +a[1] = p; // bad，数组不能赋值 +a[1][1] = (int) p; // ok + +int **ptr2level = a; // bad，类型不对 +int x = a; // bad，类型不对 + +int *p1 = a; // ok +int *p2 = &a; // ok +p1 = (int*) a; // ok +p1 = (int*) &a; // ok，这四个取到的值是一样的 +p1 = (int*) &&a; // bad，不是 lvalue +p1 = a; // bad，必须显式转换 +p1 = &a; // bad，必须显式转换 +``` + +## 步骤13 结构体 +是否必须？工作量是否过大？ + + # feature文法 小 feature 如 ternary expr ; var 以外加上 val ; 允许 var 做类型推断。 From 4cb8444b1997b48d9518184ec3e53547aba95382 Mon Sep 17 00:00:00 2001 From: Hoblovski Date: Sun, 16 Aug 2020 00:22:26 +0800 Subject: [PATCH 17/43] more on ptr/arr --- doc/minidecaf-spec.md | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 39da178..945b447 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -1081,6 +1081,17 @@ factor * 如果 `& Ident` 那直接返回 Ident 地址 * `&*expr` 等价于 `expr`，（但是不再是 lvalue 了） + +* 如果某类型的指针不指向一个该类型的对象，而且它不是空指针，这就是一个 ub，哪怕不解引用 + - 空指针指的是值为 0 的指针 + - 空指针可以存在，这不是 ub。但是不能解引用。 + - 未对齐的指针是 ub + - （step12）指针算术如果越界是 ub +* 这一步暂时不支持指针算术，因为没有数组。 + +* [TODO] 是否支持把 0 作为空指针常量？ +* [TODO] 是否支持 cast expr？ + ## 步骤12 (WIP) 数组 请完善 @@ -1100,6 +1111,17 @@ factor // b: int*[2], 那么 b[1]: int*, b[1][3]: int ``` +加入指针算术： +* 指针加法：允许指针加 int、以及 int 加指针，结果类型同指针类型。 + - （下同）int 和指针运算的时候，运算前要乘上指针类型的基类型的 sizeof + - （下同）如果越界然后解引用，ub + - 越界指的是数组越界，其中单个对象视为长度为 1 的数组 +* 指针减法：允许指针减 int、以及指针减指针。 + - 指针减 int 结果类型同指针类型 + - 指针 `a` 减指针 `b` 的结果是一个 int `c`，满足 `a == b + c`。同上，不对齐指针是 ub + - 指针 `a` 减指针 `b`，只有当 `a` 和 `b` 是指向同一个数组内元素（不越界，或者刚刚超过最后那个元素一个位置）时才有意义 +* 空指针参与的任何指针算术都是 ub + 并且： * 没有变长数组 `int a[n];` 也没有不定长数组 `int a[];` - 否则预留空间和计算偏移量更麻烦——可以作为较复杂的小练习 From 58086d1c4fd2158a5e4f694c2e325e293f36f847 Mon Sep 17 00:00:00 2001 From: Shizhi Tang Date: Sun, 16 Aug 2020 15:08:40 +0800 Subject: [PATCH 18/43] update spec 2 step 1 - 10 --- doc/minidecaf-spec.md | 130 +++++++++++++++++++++++++++++++++--------- 1 file changed, 102 insertions(+), 28 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 945b447..65c8e06 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -1,4 +1,3 @@ - # 第一种选择 缺点：step1-10的input还不是正常的C程序 @@ -266,19 +265,25 @@ typ = ("int" | "char") "*"* ``` ::= - ::= "int" "(" ")" "{" "}" -< ::= "return" ";" | "int" "=" ";" + ::= "int" "main" "(" ")" "{" "}" + ::= "return" ";" ::= ``` 例子： + ``` int main() { return 2; } ``` +语义规定： + +- 为尽可能兼容指针，本实验中所有`int`类型均为64位长度。 + 对应的Token为： + ``` Open brace { Close brace } @@ -287,13 +292,13 @@ Close parenthesis \) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* Integer literal [0-9]+ +Main keyword main ``` 对应的AST为： ``` program = Program(function_declaration) -function_declaration = Function(string, statement) //string is the function name +function_declaration = Function("main", statement) statement = Return(exp) | Assign(variable, exp) exp = Constant(int) ``` @@ -303,7 +308,7 @@ exp = Constant(int) ``` ::= - ::= "int" "(" ")" "{" "}" + ::= "int" "main" "(" ")" "{" "}" ::= "return" ";" ::= | ::= "!" | "~" | "-" @@ -325,38 +330,40 @@ Close parenthesis \) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* Integer literal [0-9]+ Negation - Bitwise complement ~ Logical negation ! +Main keyword main ``` 对应的AST为： ``` program = Program(function_declaration) -function_declaration = Function(string, statement) //string is the function name +function_declaration = Function("main", statement) statement = Return(exp) exp = UnOp(operator, exp) | Constant(int) ``` ## 步骤3：Binary Operators and Parenthesis for ( expr ) 支持 + ``` Addition + Subtraction - Multiplication * Division / +Modular % ``` 语言语法为： ``` ::= - ::= "int" "(" ")" "{" "}" + ::= "int" "main" "(" ")" "{" "}" ::= "return" ";" ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | ::= "!" | "~" | "-" ``` @@ -370,7 +377,6 @@ Close parenthesis ) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* Integer literal [0-9]+ Minus - Bitwise complement ~ @@ -378,12 +384,13 @@ Logical negation ! Addition + Multiplication * Division / +Main keyword main ``` 对应的AST为： ``` program = Program(function_declaration) -function_declaration = Function(string, statement) //string is the function name +function_declaration = Function("main", statement) statement = Return(exp) exp = BinOp(binary_operator, exp, exp) | UnOp(unary_operator, exp) @@ -392,6 +399,7 @@ exp = BinOp(binary_operator, exp, exp) ## 步骤4：Logical Binary Operators 支持 + ``` Logical AND && Logical OR || @@ -406,7 +414,7 @@ Greater than or equal to >= ``` ::= - ::= "int" "(" ")" "{" "}" + ::= "int" "main" "(" ")" "{" "}" ::= "return" ";" ::= { "||" } ::= { "&&" } @@ -417,7 +425,20 @@ Greater than or equal to >= ::= "(" ")" | | ::= "!" | "~" | "-" ``` +语义规定： + +- 本实验中是否实现短路求值不做要求，即属于未定义行为。例如，在后续步骤引入局部变量后可能出现如下程序： + + ``` + int x = 0; + int a = 1 || (x = 1); + return x; + ``` + + 返回 0 或 1 均被接受。 + 对应的Token为： + ``` Open brace { Close brace } @@ -426,7 +447,6 @@ Close parenthesis ) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* Integer literal [0-9]+ Minus - Bitwise complement ~ @@ -442,11 +462,12 @@ Less than < Less than or equal <= Greater than > Greater than or equal >= +Main keyword main ``` 对应的AST为： ``` program = Program(function_declaration) -function_declaration = Function(string, statement) //string is the function name +function_declaration = Function("main", statement) statement = Return(exp) exp = BinOp(binary_operator, exp, exp) | UnOp(unary_operator, exp) @@ -455,6 +476,7 @@ exp = BinOp(binary_operator, exp, exp) ## 步骤5：Local Variables 支持Local Variables + ``` int a; a=3; @@ -478,7 +500,14 @@ a=3; ::= "(" ")" | | | ::= "!" | "~" | "-" ``` +> 注意：本步骤中 `main` 函数的函数名不再是一个关键字，而是与变量名同属于 ID。这意味着名为 `main` 的局部变量是合法的。 + +语义规定： + +- 若函数中缺少`return` 语句，则一律返回0。 + 对应的Token为： + ``` Open brace { Close brace } @@ -487,7 +516,7 @@ Close parenthesis ) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ Minus - Bitwise complement ~ @@ -523,6 +552,7 @@ exp = Assign(string, exp) ## 步骤6：Conditional statements & expressions 例如 + ``` if (flag) { int e = a ? b : c; @@ -552,7 +582,22 @@ if (flag) { ::= "(" ")" | | | ::= "!" | "~" | "-" ``` +> 注意： `` 和 `` 的定义细节与上一步骤不完全相同。这是因为形如 `if (1) int x;` 的语句是非法的。 + +语义规定： + +- `?:`操作符应具有短路性质。例如 + + ``` + int x = 0; + int a = 1 ? 2 : (x = 1); + return x; + ``` + + 应返回 0。 + 对应的Token为： + ``` Open brace { Close brace } @@ -561,7 +606,7 @@ Close parenthesis ) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ Minus - Bitwise complement ~ @@ -608,15 +653,17 @@ exp = Assign(string, exp) | CondExp(exp, exp, exp) //the three expressions are the condition, 'if' expression and 'else' expression, respectively ``` -## 步骤7：Compound Statements +## 步骤7：Compound Statements and Definition Scope 例如 + ``` int main() { - int a; + int a = 2; { - //this is also a compound statement! - a = 4; + int a; + a = 4; // here a == 4 } + // here a == 2 } ``` 语言语法为： @@ -641,7 +688,12 @@ int main() { ::= "(" ")" | | | ::= "!" | "~" | "-" ``` +语义说明： + +- 局部变量的作用域开始于**局部变量定义之处**（而不是语句块开始处），结束于**所在语句块末尾**。因此，程序片段 `int a = 1; { return a; int a = 2;}` 应返回 1 而不是 2。 + 对应的Token为（不变）： + ``` Open brace { Close brace } @@ -650,7 +702,7 @@ Close parenthesis ) Semicolon ; Int keyword int Return keyword return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ Minus - Bitwise complement ~ @@ -700,6 +752,7 @@ exp = Assign(string, exp) ## 步骤8：Loops 例如 + ``` int i; for (i = 0; i < 10; i = i + 1) { @@ -721,10 +774,10 @@ while (i < 10) { | // null statement | "if" "(" ")" [ "else" ] | "{" { } "} - | "for" "(" ")" - | "for" "(" ")" + | "for" "(" + | "for" "(" | "while" "(" ")" - | "do" "while" ";" + | "do" "while" "(" ")" ";" | "break" ";" | "continue" ";" ::= ";" | ";" @@ -740,7 +793,14 @@ while (i < 10) { ::= "(" ")" | | | ::= "!" | "~" | "-" ``` +语义说明： + +- 每个`for`循环意味着一个隐式的局部变量作用域。`...; for (...; ...; ...) { ... } ...;` 事实上等价于 `...; { for (...; ...; ...) { ... } } ...;` 。 + +> 注意：程序片段 `for(int i;;) { int i; }` 的两个局部变量分属内外两个不同的作用域内，因此是合法的。 + 对应的Token为： + ``` { } @@ -749,7 +809,7 @@ while (i < 10) { ; int return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ - ~ @@ -809,6 +869,7 @@ exp = Assign(string, exp) ``` ## 步骤9：Functions 例如 + ``` int three() { return 3; @@ -849,7 +910,12 @@ int main() { ::= id "(" [ { "," } ] ")" ::= "!" | "~" | "-" ``` +语义说明： + +- 本实验对于同名函数的重复声明不做要求，即属于未定义行为。测例中不会出现同名函数重复声明的情况。 + 对应的Token为： + ``` { } @@ -858,7 +924,7 @@ int main() { ; int return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ - ~ @@ -921,6 +987,7 @@ exp = Assign(string, exp) ## 步骤10：Global Variables 例如 + ``` int foo; @@ -970,7 +1037,14 @@ int main() { ::= "!" | "~" | "-" ``` +语义说明： + +- 本实验对同名全局变量的重复定义不做要求，即属于未定义行为。测例中不会出现同名全局变量的重复定义。 +- 全局变量若没有初始化，则默认初始化为0。 +- 编译器只需实现用常数初始化全局变量，而无需实现表达式初始化。（但局部变量应能使用表达式初始化） + 对应的Token为(不变)： + ``` { } @@ -979,7 +1053,7 @@ int main() { ; int return -Identifier [a-zA-Z]\w* +Identifier [a-zA-Z_][a-zA-Z0-9_]* Integer literal [0-9]+ - ~ From 6856b755661cf66105606ddb6c75692277c2aebd Mon Sep 17 00:00:00 2001 From: chyyuu Date: Thu, 20 Aug 2020 09:43:53 +0800 Subject: [PATCH 19/43] Update README.md --- README.md | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/README.md b/README.md index df3ee22..a315b51 100644 --- a/README.md +++ b/README.md @@ -1,5 +1,7 @@ # minidecaf -## status -### 2020.07.28: -- cy: step 11 finished. + +## Reference: +- [nqcc](https://github.com/nlsandler/nqcc) + + From de881928e4093c8c39b67f290e1dab343251a3b0 Mon Sep 17 00:00:00 2001 From: Shizhi Tang Date: Mon, 24 Aug 2020 10:49:06 +0800 Subject: [PATCH 20/43] -> Integer, -> Identifier --- doc/minidecaf-spec.md | 58 +++++++++++++++++++++---------------------- 1 file changed, 29 insertions(+), 29 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 65c8e06..996a7b4 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -266,8 +266,8 @@ typ = ("int" | "char") "*"* ``` ::= ::= "int" "main" "(" ")" "{" "}" - ::= "return" ";" - ::= + ::= "return" Integer ";" + ::= Integer ``` 例子： @@ -310,7 +310,7 @@ exp = Constant(int) ::= ::= "int" "main" "(" ")" "{" "}" ::= "return" ";" - ::= | + ::= | Integer ::= "!" | "~" | "-" ``` @@ -364,7 +364,7 @@ Modular % ::= "return" ";" ::= { ("+" | "-") } ::= { ("*" | "/" | "%") } - ::= "(" ")" | | + ::= "(" ")" | | Integer ::= "!" | "~" | "-" ``` @@ -422,7 +422,7 @@ Greater than or equal to >= ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= "(" ")" | | + ::= "(" ")" | | Integer ::= "!" | "~" | "-" ``` 语义规定： @@ -486,18 +486,18 @@ a=3; ``` ::= - ::= "int" "(" ")" "{" { } "}" + ::= "int" Identifier "(" ")" "{" { } "}" ::= "return" ";" | ";" - | "int" [ = ] ";" - ::= "=" | + | "int" Identifier [ = ] ";" + ::= Identifier "=" | ::= { "||" } ::= { "&&" } ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= "(" ")" | | | + ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` > 注意：本步骤中 `main` 函数的函数名不再是一个关键字，而是与变量名同属于 ID。这意味着名为 `main` 的局部变量是合法的。 @@ -563,15 +563,15 @@ if (flag) { ``` ::= - ::= "int" "(" ")" "{" { } "}" + ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" [ = ] ";" + ::= "int" Identifier [ = ] ";" ::= "return" ";" | ";" | "if" "(" ")" [ "else" ] - ::= "=" | + ::= Identifier "=" | ::= [ "?" ":" ] ::= { "||" } ::= { "&&" } @@ -579,7 +579,7 @@ if (flag) { ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= "(" ")" | | | + ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` > 注意： `` 和 `` 的定义细节与上一步骤不完全相同。这是因为形如 `if (1) int x;` 的语句是非法的。 @@ -670,14 +670,14 @@ int main() { ``` ::= - ::= "int" "(" ")" "{" { } "}" + ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" [ = ] ";" + ::= "int" Identifier [ = ] ";" ::= "return" ";" | ";" | "if" "(" ")" [ "else" ] | "{" { } "} - ::= "=" | + ::= Identifier "=" | ::= [ "?" ":" ] ::= { "||" } ::= { "&&" } @@ -685,7 +685,7 @@ int main() { ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= "(" ")" | | | + ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` 语义说明： @@ -767,9 +767,9 @@ while (i < 10) { ``` ::= - ::= "int" "(" ")" "{" { } "}" + ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" [ = ] ";" + ::= "int" Identifier [ = ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] @@ -782,7 +782,7 @@ while (i < 10) { | "continue" ";" ::= ";" | ";" ::= ")" | ")" - ::= "=" | + ::= Identifier "=" | ::= [ "?" ":" ] ::= { "||" } ::= { "&&" } @@ -790,7 +790,7 @@ while (i < 10) { ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= "(" ")" | | | + ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` 语义说明： @@ -883,9 +883,9 @@ int main() { ``` ::= { } - ::= "int" "(" [ "int" { "," "int" } ] ")" ( "{" { } "}" | ";" ) + ::= "int" Identifier "(" [ "int" Identifier { "," "int" Identifier } ] ")" ( "{" { } "}" | ";" ) ::= | - ::= "int" [ = ] ";" + ::= "int" Identifier [ = ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] @@ -898,7 +898,7 @@ int main() { | "continue" ";" ::= ";" | ";" ::= ")" | ")" - ::= "=" | + ::= Identifier "=" | ::= [ "?" ":" ] ::= { "||" } ::= { "&&" } @@ -906,7 +906,7 @@ int main() { ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= | "(" ")" | | | + ::= | "(" ")" | | Integer | Identifier ::= id "(" [ { "," } ] ")" ::= "!" | "~" | "-" ``` @@ -1009,9 +1009,9 @@ int main() { ``` ::= { | } - ::= "int" "(" [ "int" { "," "int" } ] ")" ( "{" { } "}" | ";" ) + ::= "int" Identifier "(" [ "int" Identifier { "," "int" Identifier } ] ")" ( "{" { } "}" | ";" ) ::= | - ::= "int" [ = ] ";" + ::= "int" Identifier [ = ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] @@ -1024,7 +1024,7 @@ int main() { | "continue" ";" ::= ";" | ";" ::= ")" | ")" - ::= "=" | + ::= Identifier "=" | ::= [ "?" ":" ] ::= { "||" } ::= { "&&" } @@ -1032,7 +1032,7 @@ int main() { ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } ::= { ("*" | "/") } - ::= | "(" ")" | | | + ::= | "(" ")" | | Integer | Identifier ::= id "(" [ { "," } ] ")" ::= "!" | "~" | "-" ``` From 0e3428f3598b19ee9cc4467a0cd8fc627c76432d Mon Sep 17 00:00:00 2001 From: Shizhi Tang Date: Mon, 24 Aug 2020 11:29:17 +0800 Subject: [PATCH 21/43] fix: = -> "=" --- doc/minidecaf-spec.md | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 996a7b4..9351e03 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -489,7 +489,7 @@ a=3; ::= "int" Identifier "(" ")" "{" { } "}" ::= "return" ";" | ";" - | "int" Identifier [ = ] ";" + | "int" Identifier [ "=" ] ";" ::= Identifier "=" | ::= { "||" } ::= { "&&" } @@ -565,7 +565,7 @@ if (flag) { ::= ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" Identifier [ = ] ";" + ::= "int" Identifier [ "=" ] ";" ::= "return" ";" | ";" | "if" "(" ")" [ "else" ] @@ -672,7 +672,7 @@ int main() { ::= ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" Identifier [ = ] ";" + ::= "int" Identifier [ "=" ] ";" ::= "return" ";" | ";" | "if" "(" ")" [ "else" ] @@ -769,7 +769,7 @@ while (i < 10) { ::= ::= "int" Identifier "(" ")" "{" { } "}" ::= | - ::= "int" Identifier [ = ] ";" + ::= "int" Identifier [ "=" ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] @@ -885,7 +885,7 @@ int main() { ::= { } ::= "int" Identifier "(" [ "int" Identifier { "," "int" Identifier } ] ")" ( "{" { } "}" | ";" ) ::= | - ::= "int" Identifier [ = ] ";" + ::= "int" Identifier [ "=" ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] @@ -1011,7 +1011,7 @@ int main() { ::= { | } ::= "int" Identifier "(" [ "int" Identifier { "," "int" Identifier } ] ")" ( "{" { } "}" | ";" ) ::= | - ::= "int" Identifier [ = ] ";" + ::= "int" Identifier [ "=" ] ";" ::= "return" ";" | // null statement | "if" "(" ")" [ "else" ] From 5aa96e6dc4956d421a435a09939e2a3eb403c56d Mon Sep 17 00:00:00 2001 From: Shizhi Tang Date: Mon, 24 Aug 2020 13:10:09 +0800 Subject: [PATCH 22/43] allow empty condition in for --- doc/minidecaf-spec.md | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 9351e03..9fcea09 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -763,7 +763,7 @@ while (i < 10) { i = i + 1; } ``` -语言语法为：(注意语法和AST定义之间存在差异;语法允许for循环中的控制表达式为空，但AST不允许。) +语言语法为： ``` ::= @@ -853,8 +853,8 @@ statement = Return(exp) // first statement is 'if' block // second statement is optional 'else' block | Compound(block_item list) - | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body - | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | For(exp option, exp option, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp option, exp option, statement) // initial declaration, condition, post-expression, body | While(expression, statement) // condition, body | Do(statement, expression) // body, condition | Break @@ -969,8 +969,8 @@ statement = Return(exp) // first statement is 'if' block // second statement is optional 'else' block | Compound(block_item list) - | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body - | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | For(exp option, exp option, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp option, exp option, statement) // initial declaration, condition, post-expression, body | While(expression, statement) // condition, body | Do(statement, expression) // body, condition | Break @@ -1101,8 +1101,8 @@ statement = Return(exp) // first statement is 'if' block // second statement is optional 'else' block | Compound(block_item list) - | For(exp option, exp, exp option, statement) // initial expression, condition, post-expression, body - | ForDecl(declaration, exp, exp option, statement) // initial declaration, condition, post-expression, body + | For(exp option, exp option, exp option, statement) // initial expression, condition, post-expression, body + | ForDecl(declaration, exp option, exp option, statement) // initial declaration, condition, post-expression, body | While(expression, statement) // condition, body | Do(statement, expression) // body, condition | Break From f8e6b5281b4f2951e02700b9997b4a37fe165ac8 Mon Sep 17 00:00:00 2001 From: equation314 Date: Sat, 29 Aug 2020 01:16:50 +0800 Subject: [PATCH 23/43] update spec for step 11 & 12 --- doc/minidecaf-spec.md | 297 ++++++++++++++++++++++++++---------------- 1 file changed, 187 insertions(+), 110 deletions(-) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 9fcea09..991d9d3 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -345,7 +345,7 @@ statement = Return(exp) exp = UnOp(operator, exp) | Constant(int) ``` -## 步骤3：Binary Operators and Parenthesis for ( expr ) +## 步骤3：Binary Operators and Parenthesis for ( expr ) 支持 ``` @@ -421,7 +421,7 @@ Greater than or equal to >= ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | Integer ::= "!" | "~" | "-" ``` @@ -496,7 +496,7 @@ a=3; ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` @@ -578,7 +578,7 @@ if (flag) { ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` @@ -684,7 +684,7 @@ int main() { ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` @@ -789,7 +789,7 @@ while (i < 10) { ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= "(" ")" | | Integer | Identifier ::= "!" | "~" | "-" ``` @@ -905,9 +905,9 @@ int main() { ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= | "(" ")" | | Integer | Identifier - ::= id "(" [ { "," } ] ")" + ::= Identifier "(" [ { "," } ] ")" ::= "!" | "~" | "-" ``` 语义说明： @@ -1031,9 +1031,9 @@ int main() { ::= { ("!=" | "==") } ::= { ("<" | ">" | "<=" | ">=") } ::= { ("+" | "-") } - ::= { ("*" | "/") } + ::= { ("*" | "/" | "%") } ::= | "(" ")" | | Integer | Identifier - ::= id "(" [ { "," } ] ")" + ::= Identifier "(" [ { "," } ] ")" ::= "!" | "~" | "-" ``` @@ -1117,128 +1117,205 @@ exp = Assign(string, exp) | FunCall(string, exp list) // string is the function name ``` -## 步骤11 (WIP) 指针 - -指针和数组是否要做？ - -请完善 +## 步骤11：Pointers 主要改动部分 -``` -func - : ty Ident '(' paramList ')' (block | ';') // 参数本质就是 decl - ; - -ty - : 'int' - | ty '*' - ; - -decl - : ty Ident ('=' expr)? // 去掉了分号，之前用到的地方记得加分号 - ; +```diff + ::= { | } +- ::= "int" Identifier "(" [ "int" Identifier { "," "int" Identifier } ] ")" ( "{" { } "}" | ";" ) ++ ::= "int" | "*" ++ ::= [ Identifier { "," Identifier } ] ++ ::= Identifier "(" ")" ( "{" { } "}" | ";" ) + ::= | +- ::= "int" Identifier [ "=" ] ";" ++ ::= Identifier [ "=" ] ";" + ::= "return" ";" + | // null statement + | "if" "(" ")" [ "else" ] + | "{" { } "} + | "for" "(" ")" + | "for" "(" ")" + | "while" "(" ")" + | "do" "while" ";" + | "break" ";" + | "continue" ";" + ::= ";" | ";" + ::= ")" | ")" +- ::= Identifier "=" | ++ ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } + ::= { ("*" | "/" | "%") } +- ::= | "(" ")" | | Integer | Identifier ++ ::= | "(" ")" | | "(" ")" | Integer | Identifier + ::= Identifier "(" [ { "," } ] ")" +- ::= "!" | "~" | "-" ++ ::= "!" | "~" | "-" | "&" | "*" +``` + +一些说明： + +1. ` "=" ` 和 `"&" ` 中的 `` 要求是左值（lvalue），即不允许 `&(2+3)` 这种。lvalue 的定义如下： + * `Identifier` 和 `"*" ` 是 lvalue； + * 如果 `` 是 lvalue，`"(" ")"` 也是 lvalue。 +2. 取地址算符 `&`： + * 后面只能跟 lvalue。 + * 对于 `& Ident`，直接返回 Ident 的地址，类型是以 Ident 类型为基类型的指针。 + * `&*expr` 等价于 `expr`，但是不再是 lvalue 了。 +3. 解引用算符 `*`： + * 后面只能跟指针类型，表示取出该指针指向的地址中的值，类型为指针的基类型。 + * 返回值是 lvalue。 + * 允许放在赋值号左边：`*p = 1`。 +4. 指针运算： + * 一元运算只支持 `&` 和 `*`。 + * 二元运算目前只支持 `==` 和 `!=`，要求两边都是相同基类型的指针类型。 + * 不支持大小比较、逻辑运算。 + * 这一步暂时不支持指针算术，因为没有数组。 +5. 空指针： + * 空指针指的是值为 0 的指针。 + * 空指针可以存在，对其解引用是未定义行为。 + * 只能用 `int *p = (int*) 0;` 定义。 + * 只能用类似 `if (p == (int*) 0) {}` 这样的判断是否为空。 +6. 类型转换： + * 没有隐式类型转换，所有赋值、运算、传参等都要求类型完全匹配。 + * 允许 int、不同类型的指针之间的任何显式转换。 +7. 其他： + * 所有指针类型的变量的大小都是 4 个字节（RV32）。 + * 如果某类型的指针不指向一个该类型的对象，而且它不是空指针，这就是一个未定义行为，哪怕不解引用。 + * 未对齐的指针是未定义行为。 -paramList - : (decl (',' decl)*)? // 逗号隔开的 decl，并且语义检查 decl 不能有初始值 - ; - -factor - : ... - | '&' factor // 要做类型和 lvalue 检查，不允许 &(2+3) 这种 - // lvalue : Ident | '*' expr - | '*' factor // 要做类型检查 - ; -``` +例子： -其中取地址算符 `&` 要求 -* 如果 `& Ident` 那直接返回 Ident 地址 -* `&*expr` 等价于 `expr`，（但是不再是 lvalue 了） +```c +int a = 1; // a == 1 +*&a = 2; // a == 2 +(*(&(a))) = 3; // a == 3 +int *p = &a; +*p = 4; // a == 4 -* 如果某类型的指针不指向一个该类型的对象，而且它不是空指针，这就是一个 ub，哪怕不解引用 - - 空指针指的是值为 0 的指针 - - 空指针可以存在，这不是 ub。但是不能解引用。 - - 未对齐的指针是 ub - - （step12）指针算术如果越界是 ub -* 这一步暂时不支持指针算术，因为没有数组。 +int **q = &p; +**q = 5; // a == 5 -* [TODO] 是否支持把 0 作为空指针常量？ -* [TODO] 是否支持 cast expr？ +q = &(&a); // bad，&a 不是 lvalue +q = &(*p); // bad，类型不对 +p = &*p; // ok -## 步骤12 (WIP) 数组 +int *null = (int*) 0; // 空指针 +if (p == (int*) 0 || (int) p == 0) { + // ... +} else if (p != null) { + // ... +} +``` -请完善 +## 步骤12：Arrays 主要改动部分 -``` -decl - : ty Ident ('[' Integer ']')* ('=' expr)? // 语义检查：数组 decl 不能给初始值 - ; - -factor - : ... - | '&' factor // lvalue : Ident | '*' expr | expr '[' expr ']' - | expr '[' expr ']' // 要做类型检查，要求第一个 expr 类型是 ty* 或者数组 - // a: int[2][3]，那么 a[1]: int[3]，a[1][2]: int - // b: int*[2], 那么 b[1]: int*, b[1][3]: int -``` - -加入指针算术： -* 指针加法：允许指针加 int、以及 int 加指针，结果类型同指针类型。 - - （下同）int 和指针运算的时候，运算前要乘上指针类型的基类型的 sizeof - - （下同）如果越界然后解引用，ub - - 越界指的是数组越界，其中单个对象视为长度为 1 的数组 -* 指针减法：允许指针减 int、以及指针减指针。 - - 指针减 int 结果类型同指针类型 - - 指针 `a` 减指针 `b` 的结果是一个 int `c`，满足 `a == b + c`。同上，不对齐指针是 ub - - 指针 `a` 减指针 `b`，只有当 `a` 和 `b` 是指向同一个数组内元素（不越界，或者刚刚超过最后那个元素一个位置）时才有意义 -* 空指针参与的任何指针算术都是 ub - -并且： -* 没有变长数组 `int a[n];` 也没有不定长数组 `int a[];` - - 否则预留空间和计算偏移量更麻烦——可以作为较复杂的小练习 -* 没有越界检查，有负长度检查 -* 指针不能指向数组，不存在 `int (*)[2]` 这种东西 - - 否则声明会很麻烦，如 `int (*a)[2]` 和 `int *a[2]` -* 数组初始化只能是默认零初始化，没字面量也不能 `int a[2] = {2, 3}` - - 否则麻烦 -* 数组可以在栈上或者 .bss（全局变量）里 -* 如果数组作为函数参数出现，不预留空间，否则预留空间并且零初始化 - -关于数组和指针的隐式转换 -* 只有一个地方允许指针和数组之间的隐式转换：传参，其他地方只能有数组到指针的显式类型转换 -* 如果形参类型是数组（如 `int* param[2][3]`），那么实参必须是同样的数组（`int *arg[2][3]`），或者同样基类型的指针（`int **arg`） -* 如果形参类型是指针（如 `int *param`），那么实参必须是同样的指针（`int *arg`），或者同样基类型的数组（`int arg[2]` 或 `int arg[3][10]`） +```diff + ::= { | } + ::= "int" | "*" + ::= [ Identifier { "," Identifier } ] + ::= Identifier "(" ")" ( "{" { } "}" | ";" ) + ::= | +- ::= Identifier [ "=" ] ";" ++ ::= Identifier { "[" Integer "]" } [ "=" ] ";" + ::= "return" ";" + | // null statement + | "if" "(" ")" [ "else" ] + | "{" { } "} + | "for" "(" ")" + | "for" "(" ")" + | "while" "(" ")" + | "do" "while" ";" + | "break" ";" + | "continue" ";" + ::= ";" | ";" + ::= ")" | ")" +- ::= "=" | ++ ::= "=" | + ::= [ "?" ":" ] + ::= { "||" } + ::= { "&&" } + ::= { ("!=" | "==") } + ::= { ("<" | ">" | "<=" | ">=") } + ::= { ("+" | "-") } +- ::= { ("*" | "/" | "%") } +- ::= | "(" ")" | | "(" ")" | Integer | Identifier ++ ::= { ("*" | "/" | "%") } ++ ::= | "(" ")" | ++ ::= | | "[" expr "]" ++ := Integer | Identifier | "(" ")" + ::= Identifier "(" [ { "," } ] ")" + ::= "!" | "~" | "-" | "&" | "*" +``` + +一些说明： + +1. 数组定义： + * 类型是数组类型。 + * 每一维大小不能是零或负数。 + * 没有变长数组 `int a[n];` 也没有不定长数组 `int a[];`。 + * `int *a[5];` 是 `int*` 的数组，不支持数组的指针（`int (*a)[5];`），即不支持对数组类型取地址。 + * 数组初始化只能是默认初始化，没字面量也不能 `int a[2] = {2, 3};`。 + * 数组可以作为局部变量或全局变量，在内存中是连续的，其中全局变量会进行零初始化，局部变量的初始化是未定义的。 +2. 下标运算： + * 由于下标运算为后缀形式，且优先级比一元运算符高，所以文法中要加一个 ``。 + * 只允许指针或数组类型进行下标运算，其中指针的每次下标运算等价于加上偏移后进行解引用，数组相当于把所有下标合起来算偏移，然后只进行一次解引用。 + * 下标必须是 int 类型，不进行下标越界检查，越界是未定义行为。 + * 下标运算的结果是 lvalue，即可以 `a[1] = 2; int *p = &a[1];`。 + * 允许将数组的前几维单独提出，赋给一个指针：`int a[2][2][2]; int *p = (int*) a[0]; int *q = (int*) a[1][1];`，提出后的类型还是数组类型，需要显式转换。 +3. 类型检查与转换： + * 只允许数组到任意指针类型的显式转换，不支持任何隐式转换。 + * 数组只能进行下标运算，不能参与任何其他运算，如取地址、解引用、赋值、算术、比较、逻辑等等。 + * 没有数组类型的参数，传参时只能显式转换为指针。 +3. 指针算术运算： + * 指针加法：允许指针加 int、以及 int 加指针，结果类型同指针类型。 + - int 和指针运算的时候，运算前要乘上指针类型的基类型的 sizeof。 + - 如果越界然后解引用或进行下标运算，是未定义行为。 + - 越界指的是数组越界，如果是其他类型视为长度为 1 的数组。 + * 指针减法：允许指针减 int、以及指针减指针。 + - 指针减 int 结果类型同指针类型，类似指针加法。 + - 指针 `a` 减指针 `b` 要求 `a` 和 `b` 是同类型的指针，结果是一个 int `c`，满足 `a == b + c`。同上，不对齐指针是未定义行为。 + - 指针 `a` 减指针 `b`，只有当 `a` 和 `b` 是指向同一个数组内元素（不越界，或者刚刚超过最后那个元素一个位置）时才有意义，否则是未定义行为。 + * 空指针参与的任何指针算术都是未定义行为。 例子： -``` + +```c int a[2][2]; int b[3][3]; int c[2][2]; int *p; int *q; -void matmul2(int a[2][2], int b[2][2], int c[2][2]); // ok -matmul2(a, a, c); // ok -matmul2(a, b, c); // bad 长度不匹配 -p = (int*) b; q = (int*) c; matmul2(a, p, q); // ok，有两个 int* -> int[2][2] 的隐式转换 +int matmul2(int *a, int *b, int *c); // ok +matmul2((int *)a, (int *)a, (int *)c); // ok，必须显式转换 + +int *row2 = (int*)a[1]; // ok +row2 = a[1]; // bad，int[2] -> int* 转换必须显式 + +a = p; // bad，数组不能赋值 +a[1] = p; // bad，数组不能赋值 +a[1][1] = (int) p; // ok + +int **ptr2level = a; // bad，类型不对 +int x = a; // bad，类型不对 -int *row2 = a[1]; // ok -row2 = a[1]; // bad，这里 int[2] -> int* 转换必须显式 +int *p1 = a; // bad，必须显式转换 +p1 = (int*) a; // ok -a = p; // bad，数组不能赋值 -a[1] = p; // bad，数组不能赋值 -a[1][1] = (int) p; // ok +int *p2 = &a; // bad，不能对数组取地址 +p2 = &a[0]; // bad，不能对数组取地址 +p2 = &a[0][0]; // ok -int **ptr2level = a; // bad，类型不对 -int x = a; // bad，类型不对 +int **p3 = (int **)a; // ok，这里三个 ok 的 p1, p2, p3 值应该相同，都是 a 的地址 -int *p1 = a; // ok -int *p2 = &a; // ok -p1 = (int*) a; // ok -p1 = (int*) &a; // ok，这四个取到的值是一样的 -p1 = (int*) &&a; // bad，不是 lvalue -p1 = a; // bad，必须显式转换 -p1 = &a; // bad，必须显式转换 +p1[0] = p2[1] = 1; // ok +p3[0][0] = 2; // ok，但不同于 a[0][0]，这里进行了两次解引用，是未定义行为 ``` ## 步骤13 结构体 From 01e8293368c94bb00e59e50943e1c8f9603a9fbc Mon Sep 17 00:00:00 2001 From: Shizhi Tang Date: Mon, 31 Aug 2020 16:50:47 +0800 Subject: [PATCH 24/43] Add modulo token --- doc/minidecaf-spec.md | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/doc/minidecaf-spec.md b/doc/minidecaf-spec.md index 991d9d3..f628171 100644 --- a/doc/minidecaf-spec.md +++ b/doc/minidecaf-spec.md @@ -384,6 +384,7 @@ Logical negation ! Addition + Multiplication * Division / +Modulo % Main keyword main ``` @@ -454,6 +455,7 @@ Logical negation ! Addition + Multiplication * Division / +Modulo % AND && OR || Equal == @@ -524,6 +526,7 @@ Logical negation ! Addition + Multiplication * Division / +Modulo % AND && OR || Equal == @@ -614,6 +617,7 @@ Logical negation ! Addition + Multiplication * Division / +Modulo % AND && OR || Equal == @@ -710,6 +714,7 @@ Logical negation ! Addition + Multiplication * Division / +Modulo % AND && OR || Equal == @@ -817,6 +822,7 @@ Integer literal [0-9]+ + * / +% && || == @@ -932,6 +938,7 @@ Integer literal [0-9]+ + * / +% && || == @@ -1061,6 +1068,7 @@ Integer literal [0-9]+ + * / +% && || == From a87c48dfbc5fe3df1606a03b730c900c29f4c093 Mon Sep 17 00:00:00 2001 From: dangerggg <780110073@qq.com> Date: Sun, 30 Aug 2020 17:33:00 +0800 Subject: [PATCH 25/43] Set up env: Antlr runtime & CMakeFile --- .gitignore | 61 +- CMakeLists.txt | 55 + .../antlr4-runtime/ANTLRErrorListener.cpp | 10 + .../antlr4-runtime/ANTLRErrorListener.h | 167 ++ .../antlr4-runtime/ANTLRErrorStrategy.cpp | 10 + .../antlr4-runtime/ANTLRErrorStrategy.h | 121 ++ .../antlr4-runtime/ANTLRFileStream.cpp | 34 + third_party/antlr4-runtime/ANTLRFileStream.h | 27 + .../antlr4-runtime/ANTLRInputStream.cpp | 155 ++ third_party/antlr4-runtime/ANTLRInputStream.h | 69 + .../antlr4-runtime/BailErrorStrategy.cpp | 61 + .../antlr4-runtime/BailErrorStrategy.h | 59 + .../antlr4-runtime/BaseErrorListener.cpp | 25 + .../antlr4-runtime/BaseErrorListener.h | 36 + .../antlr4-runtime/BufferedTokenStream.cpp | 414 +++++ .../antlr4-runtime/BufferedTokenStream.h | 200 +++ third_party/antlr4-runtime/CharStream.cpp | 11 + third_party/antlr4-runtime/CharStream.h | 37 + third_party/antlr4-runtime/CommonToken.cpp | 195 +++ third_party/antlr4-runtime/CommonToken.h | 158 ++ .../antlr4-runtime/CommonTokenFactory.cpp | 39 + .../antlr4-runtime/CommonTokenFactory.h | 74 + .../antlr4-runtime/CommonTokenStream.cpp | 78 + .../antlr4-runtime/CommonTokenStream.h | 79 + .../antlr4-runtime/ConsoleErrorListener.cpp | 15 + .../antlr4-runtime/ConsoleErrorListener.h | 35 + .../antlr4-runtime/DefaultErrorStrategy.cpp | 333 ++++ .../antlr4-runtime/DefaultErrorStrategy.h | 466 ++++++ .../DiagnosticErrorListener.cpp | 84 + .../antlr4-runtime/DiagnosticErrorListener.h | 80 + third_party/antlr4-runtime/Exceptions.cpp | 64 + third_party/antlr4-runtime/Exceptions.h | 99 ++ .../FailedPredicateException.cpp | 51 + .../antlr4-runtime/FailedPredicateException.h | 32 + .../antlr4-runtime/InputMismatchException.cpp | 18 + .../antlr4-runtime/InputMismatchException.h | 24 + third_party/antlr4-runtime/IntStream.cpp | 12 + third_party/antlr4-runtime/IntStream.h | 218 +++ .../antlr4-runtime/InterpreterRuleContext.cpp | 19 + .../antlr4-runtime/InterpreterRuleContext.h | 45 + third_party/antlr4-runtime/Lexer.cpp | 295 ++++ third_party/antlr4-runtime/Lexer.h | 196 +++ .../antlr4-runtime/LexerInterpreter.cpp | 75 + third_party/antlr4-runtime/LexerInterpreter.h | 52 + .../LexerNoViableAltException.cpp | 36 + .../LexerNoViableAltException.h | 31 + .../antlr4-runtime/ListTokenSource.cpp | 92 ++ third_party/antlr4-runtime/ListTokenSource.h | 88 ++ .../antlr4-runtime/NoViableAltException.cpp | 46 + .../antlr4-runtime/NoViableAltException.h | 42 + third_party/antlr4-runtime/Parser.cpp | 648 ++++++++ third_party/antlr4-runtime/Parser.h | 467 ++++++ .../antlr4-runtime/ParserInterpreter.cpp | 306 ++++ .../antlr4-runtime/ParserInterpreter.h | 179 +++ .../antlr4-runtime/ParserRuleContext.cpp | 141 ++ .../antlr4-runtime/ParserRuleContext.h | 147 ++ .../antlr4-runtime/ProxyErrorListener.cpp | 53 + .../antlr4-runtime/ProxyErrorListener.h | 38 + .../antlr4-runtime/RecognitionException.cpp | 66 + .../antlr4-runtime/RecognitionException.h | 98 ++ third_party/antlr4-runtime/Recognizer.cpp | 167 ++ third_party/antlr4-runtime/Recognizer.h | 164 ++ third_party/antlr4-runtime/RuleContext.cpp | 143 ++ third_party/antlr4-runtime/RuleContext.h | 137 ++ .../antlr4-runtime/RuleContextWithAltNum.cpp | 27 + .../antlr4-runtime/RuleContextWithAltNum.h | 32 + .../antlr4-runtime/RuntimeMetaData.cpp | 53 + third_party/antlr4-runtime/RuntimeMetaData.h | 155 ++ third_party/antlr4-runtime/Token.cpp | 9 + third_party/antlr4-runtime/Token.h | 92 ++ third_party/antlr4-runtime/TokenFactory.h | 30 + third_party/antlr4-runtime/TokenSource.cpp | 9 + third_party/antlr4-runtime/TokenSource.h | 85 + third_party/antlr4-runtime/TokenStream.cpp | 11 + third_party/antlr4-runtime/TokenStream.h | 137 ++ .../antlr4-runtime/TokenStreamRewriter.cpp | 425 +++++ .../antlr4-runtime/TokenStreamRewriter.h | 293 ++++ .../antlr4-runtime/UnbufferedCharStream.cpp | 211 +++ .../antlr4-runtime/UnbufferedCharStream.h | 123 ++ .../antlr4-runtime/UnbufferedTokenStream.cpp | 270 ++++ .../antlr4-runtime/UnbufferedTokenStream.h | 115 ++ third_party/antlr4-runtime/Vocabulary.cpp | 104 ++ third_party/antlr4-runtime/Vocabulary.h | 193 +++ third_party/antlr4-runtime/WritableToken.cpp | 9 + third_party/antlr4-runtime/WritableToken.h | 23 + third_party/antlr4-runtime/antlr4-common.h | 137 ++ third_party/antlr4-runtime/antlr4-runtime.h | 167 ++ third_party/antlr4-runtime/atn/ATN.cpp | 209 +++ third_party/antlr4-runtime/atn/ATN.h | 112 ++ third_party/antlr4-runtime/atn/ATNConfig.cpp | 113 ++ third_party/antlr4-runtime/atn/ATNConfig.h | 148 ++ .../antlr4-runtime/atn/ATNConfigSet.cpp | 228 +++ third_party/antlr4-runtime/atn/ATNConfigSet.h | 110 ++ .../atn/ATNDeserializationOptions.cpp | 64 + .../atn/ATNDeserializationOptions.h | 50 + .../antlr4-runtime/atn/ATNDeserializer.cpp | 758 +++++++++ .../antlr4-runtime/atn/ATNDeserializer.h | 85 + .../antlr4-runtime/atn/ATNSerializer.cpp | 621 ++++++++ .../antlr4-runtime/atn/ATNSerializer.h | 61 + .../antlr4-runtime/atn/ATNSimulator.cpp | 63 + third_party/antlr4-runtime/atn/ATNSimulator.h | 87 ++ third_party/antlr4-runtime/atn/ATNState.cpp | 72 + third_party/antlr4-runtime/atn/ATNState.h | 133 ++ third_party/antlr4-runtime/atn/ATNType.h | 20 + .../atn/AbstractPredicateTransition.cpp | 14 + .../atn/AbstractPredicateTransition.h | 24 + .../antlr4-runtime/atn/ActionTransition.cpp | 33 + .../antlr4-runtime/atn/ActionTransition.h | 33 + .../antlr4-runtime/atn/AmbiguityInfo.cpp | 16 + .../antlr4-runtime/atn/AmbiguityInfo.h | 68 + .../atn/ArrayPredictionContext.cpp | 82 + .../atn/ArrayPredictionContext.h | 43 + .../antlr4-runtime/atn/AtomTransition.cpp | 31 + .../antlr4-runtime/atn/AtomTransition.h | 30 + .../atn/BasicBlockStartState.cpp | 12 + .../antlr4-runtime/atn/BasicBlockStartState.h | 22 + third_party/antlr4-runtime/atn/BasicState.cpp | 12 + third_party/antlr4-runtime/atn/BasicState.h | 21 + .../antlr4-runtime/atn/BlockEndState.cpp | 15 + .../antlr4-runtime/atn/BlockEndState.h | 24 + .../antlr4-runtime/atn/BlockStartState.cpp | 9 + .../antlr4-runtime/atn/BlockStartState.h | 21 + .../atn/ContextSensitivityInfo.cpp | 14 + .../atn/ContextSensitivityInfo.h | 47 + .../antlr4-runtime/atn/DecisionEventInfo.cpp | 14 + .../antlr4-runtime/atn/DecisionEventInfo.h | 70 + .../antlr4-runtime/atn/DecisionInfo.cpp | 25 + third_party/antlr4-runtime/atn/DecisionInfo.h | 227 +++ .../antlr4-runtime/atn/DecisionState.cpp | 17 + .../antlr4-runtime/atn/DecisionState.h | 30 + .../atn/EmptyPredictionContext.cpp | 35 + .../atn/EmptyPredictionContext.h | 27 + .../antlr4-runtime/atn/EpsilonTransition.cpp | 35 + .../antlr4-runtime/atn/EpsilonTransition.h | 39 + third_party/antlr4-runtime/atn/ErrorInfo.cpp | 15 + third_party/antlr4-runtime/atn/ErrorInfo.h | 43 + .../antlr4-runtime/atn/LL1Analyzer.cpp | 158 ++ third_party/antlr4-runtime/atn/LL1Analyzer.h | 109 ++ .../antlr4-runtime/atn/LexerATNConfig.cpp | 84 + .../antlr4-runtime/atn/LexerATNConfig.h | 44 + .../antlr4-runtime/atn/LexerATNSimulator.cpp | 628 ++++++++ .../antlr4-runtime/atn/LexerATNSimulator.h | 210 +++ .../antlr4-runtime/atn/LexerAction.cpp | 9 + third_party/antlr4-runtime/atn/LexerAction.h | 66 + .../atn/LexerActionExecutor.cpp | 107 ++ .../antlr4-runtime/atn/LexerActionExecutor.h | 115 ++ .../antlr4-runtime/atn/LexerActionType.h | 55 + .../antlr4-runtime/atn/LexerChannelAction.cpp | 55 + .../antlr4-runtime/atn/LexerChannelAction.h | 63 + .../antlr4-runtime/atn/LexerCustomAction.cpp | 62 + .../antlr4-runtime/atn/LexerCustomAction.h | 87 ++ .../atn/LexerIndexedCustomAction.cpp | 63 + .../atn/LexerIndexedCustomAction.h | 82 + .../antlr4-runtime/atn/LexerModeAction.cpp | 56 + .../antlr4-runtime/atn/LexerModeAction.h | 61 + .../antlr4-runtime/atn/LexerMoreAction.cpp | 47 + .../antlr4-runtime/atn/LexerMoreAction.h | 57 + .../antlr4-runtime/atn/LexerPopModeAction.cpp | 47 + .../antlr4-runtime/atn/LexerPopModeAction.h | 57 + .../atn/LexerPushModeAction.cpp | 56 + .../antlr4-runtime/atn/LexerPushModeAction.h | 61 + .../antlr4-runtime/atn/LexerSkipAction.cpp | 47 + .../antlr4-runtime/atn/LexerSkipAction.h | 55 + .../antlr4-runtime/atn/LexerTypeAction.cpp | 56 + .../antlr4-runtime/atn/LexerTypeAction.h | 55 + .../antlr4-runtime/atn/LookaheadEventInfo.cpp | 16 + .../antlr4-runtime/atn/LookaheadEventInfo.h | 42 + .../antlr4-runtime/atn/LoopEndState.cpp | 12 + third_party/antlr4-runtime/atn/LoopEndState.h | 22 + .../antlr4-runtime/atn/NotSetTransition.cpp | 27 + .../antlr4-runtime/atn/NotSetTransition.h | 25 + .../atn/OrderedATNConfigSet.cpp | 12 + .../antlr4-runtime/atn/OrderedATNConfigSet.h | 20 + third_party/antlr4-runtime/atn/ParseInfo.cpp | 102 ++ third_party/antlr4-runtime/atn/ParseInfo.h | 102 ++ .../antlr4-runtime/atn/ParserATNSimulator.cpp | 1366 +++++++++++++++++ .../antlr4-runtime/atn/ParserATNSimulator.h | 904 +++++++++++ .../atn/PlusBlockStartState.cpp | 12 + .../antlr4-runtime/atn/PlusBlockStartState.h | 25 + .../antlr4-runtime/atn/PlusLoopbackState.cpp | 12 + .../antlr4-runtime/atn/PlusLoopbackState.h | 22 + .../atn/PrecedencePredicateTransition.cpp | 32 + .../atn/PrecedencePredicateTransition.h | 29 + .../antlr4-runtime/atn/PredicateEvalInfo.cpp | 17 + .../antlr4-runtime/atn/PredicateEvalInfo.h | 62 + .../atn/PredicateTransition.cpp | 34 + .../antlr4-runtime/atn/PredicateTransition.h | 39 + .../antlr4-runtime/atn/PredictionContext.cpp | 662 ++++++++ .../antlr4-runtime/atn/PredictionContext.h | 254 +++ .../antlr4-runtime/atn/PredictionMode.cpp | 201 +++ .../antlr4-runtime/atn/PredictionMode.h | 436 ++++++ .../atn/ProfilingATNSimulator.cpp | 179 +++ .../atn/ProfilingATNSimulator.h | 60 + .../antlr4-runtime/atn/RangeTransition.cpp | 30 + .../antlr4-runtime/atn/RangeTransition.h | 29 + .../antlr4-runtime/atn/RuleStartState.cpp | 16 + .../antlr4-runtime/atn/RuleStartState.h | 25 + .../antlr4-runtime/atn/RuleStopState.cpp | 12 + .../antlr4-runtime/atn/RuleStopState.h | 25 + .../antlr4-runtime/atn/RuleTransition.cpp | 37 + .../antlr4-runtime/atn/RuleTransition.h | 40 + .../antlr4-runtime/atn/SemanticContext.cpp | 377 +++++ .../antlr4-runtime/atn/SemanticContext.h | 222 +++ .../antlr4-runtime/atn/SetTransition.cpp | 32 + .../antlr4-runtime/atn/SetTransition.h | 30 + .../atn/SingletonPredictionContext.cpp | 81 + .../atn/SingletonPredictionContext.h | 36 + .../atn/StarBlockStartState.cpp | 12 + .../antlr4-runtime/atn/StarBlockStartState.h | 21 + .../antlr4-runtime/atn/StarLoopEntryState.cpp | 15 + .../antlr4-runtime/atn/StarLoopEntryState.h | 35 + .../antlr4-runtime/atn/StarLoopbackState.cpp | 19 + .../antlr4-runtime/atn/StarLoopbackState.h | 21 + .../antlr4-runtime/atn/TokensStartState.cpp | 12 + .../antlr4-runtime/atn/TokensStartState.h | 21 + third_party/antlr4-runtime/atn/Transition.cpp | 44 + third_party/antlr4-runtime/atn/Transition.h | 76 + .../antlr4-runtime/atn/WildcardTransition.cpp | 25 + .../antlr4-runtime/atn/WildcardTransition.h | 25 + third_party/antlr4-runtime/dfa/DFA.cpp | 127 ++ third_party/antlr4-runtime/dfa/DFA.h | 91 ++ .../antlr4-runtime/dfa/DFASerializer.cpp | 67 + .../antlr4-runtime/dfa/DFASerializer.h | 32 + third_party/antlr4-runtime/dfa/DFAState.cpp | 100 ++ third_party/antlr4-runtime/dfa/DFAState.h | 144 ++ .../antlr4-runtime/dfa/LexerDFASerializer.cpp | 20 + .../antlr4-runtime/dfa/LexerDFASerializer.h | 23 + .../misc/InterpreterDataReader.cpp | 124 ++ .../misc/InterpreterDataReader.h | 31 + third_party/antlr4-runtime/misc/Interval.cpp | 89 ++ third_party/antlr4-runtime/misc/Interval.h | 84 + .../antlr4-runtime/misc/IntervalSet.cpp | 521 +++++++ third_party/antlr4-runtime/misc/IntervalSet.h | 198 +++ .../antlr4-runtime/misc/MurmurHash.cpp | 134 ++ third_party/antlr4-runtime/misc/MurmurHash.h | 76 + third_party/antlr4-runtime/misc/Predicate.cpp | 4 + third_party/antlr4-runtime/misc/Predicate.h | 21 + third_party/antlr4-runtime/support/Any.cpp | 13 + third_party/antlr4-runtime/support/Any.h | 170 ++ third_party/antlr4-runtime/support/Arrays.cpp | 43 + third_party/antlr4-runtime/support/Arrays.h | 110 ++ third_party/antlr4-runtime/support/BitSet.h | 76 + .../antlr4-runtime/support/CPPUtils.cpp | 248 +++ third_party/antlr4-runtime/support/CPPUtils.h | 78 + .../antlr4-runtime/support/Declarations.h | 163 ++ .../antlr4-runtime/support/StringUtils.cpp | 36 + .../antlr4-runtime/support/StringUtils.h | 54 + third_party/antlr4-runtime/support/guid.cpp | 303 ++++ third_party/antlr4-runtime/support/guid.h | 112 ++ .../tree/AbstractParseTreeVisitor.h | 128 ++ third_party/antlr4-runtime/tree/ErrorNode.cpp | 9 + third_party/antlr4-runtime/tree/ErrorNode.h | 19 + .../antlr4-runtime/tree/ErrorNodeImpl.cpp | 23 + .../antlr4-runtime/tree/ErrorNodeImpl.h | 33 + .../tree/IterativeParseTreeWalker.cpp | 71 + .../tree/IterativeParseTreeWalker.h | 53 + third_party/antlr4-runtime/tree/ParseTree.cpp | 15 + third_party/antlr4-runtime/tree/ParseTree.h | 102 ++ .../antlr4-runtime/tree/ParseTreeListener.cpp | 9 + .../antlr4-runtime/tree/ParseTreeListener.h | 39 + .../antlr4-runtime/tree/ParseTreeProperty.h | 50 + .../antlr4-runtime/tree/ParseTreeVisitor.cpp | 9 + .../antlr4-runtime/tree/ParseTreeVisitor.h | 57 + .../antlr4-runtime/tree/ParseTreeWalker.cpp | 49 + .../antlr4-runtime/tree/ParseTreeWalker.h | 31 + .../antlr4-runtime/tree/TerminalNode.cpp | 9 + .../antlr4-runtime/tree/TerminalNode.h | 32 + .../antlr4-runtime/tree/TerminalNodeImpl.cpp | 57 + .../antlr4-runtime/tree/TerminalNodeImpl.h | 33 + third_party/antlr4-runtime/tree/Trees.cpp | 241 +++ third_party/antlr4-runtime/tree/Trees.h | 78 + .../antlr4-runtime/tree/pattern/Chunk.cpp | 9 + .../antlr4-runtime/tree/pattern/Chunk.h | 44 + .../tree/pattern/ParseTreeMatch.cpp | 69 + .../tree/pattern/ParseTreeMatch.h | 132 ++ .../tree/pattern/ParseTreePattern.cpp | 64 + .../tree/pattern/ParseTreePattern.h | 105 ++ .../tree/pattern/ParseTreePatternMatcher.cpp | 371 +++++ .../tree/pattern/ParseTreePatternMatcher.h | 185 +++ .../tree/pattern/RuleTagToken.cpp | 77 + .../tree/pattern/RuleTagToken.h | 117 ++ .../antlr4-runtime/tree/pattern/TagChunk.cpp | 39 + .../antlr4-runtime/tree/pattern/TagChunk.h | 86 ++ .../antlr4-runtime/tree/pattern/TextChunk.cpp | 28 + .../antlr4-runtime/tree/pattern/TextChunk.h | 51 + .../tree/pattern/TokenTagToken.cpp | 36 + .../tree/pattern/TokenTagToken.h | 80 + .../antlr4-runtime/tree/xpath/XPath.cpp | 154 ++ third_party/antlr4-runtime/tree/xpath/XPath.h | 86 ++ .../tree/xpath/XPathElement.cpp | 31 + .../antlr4-runtime/tree/xpath/XPathElement.h | 40 + .../antlr4-runtime/tree/xpath/XPathLexer.cpp | 173 +++ .../antlr4-runtime/tree/xpath/XPathLexer.g4 | 64 + .../antlr4-runtime/tree/xpath/XPathLexer.h | 56 + .../tree/xpath/XPathLexerErrorListener.cpp | 13 + .../tree/xpath/XPathLexerErrorListener.h | 22 + .../tree/xpath/XPathRuleAnywhereElement.cpp | 20 + .../tree/xpath/XPathRuleAnywhereElement.h | 27 + .../tree/xpath/XPathRuleElement.cpp | 30 + .../tree/xpath/XPathRuleElement.h | 26 + .../tree/xpath/XPathTokenAnywhereElement.cpp | 20 + .../tree/xpath/XPathTokenAnywhereElement.h | 25 + .../tree/xpath/XPathTokenElement.cpp | 33 + .../tree/xpath/XPathTokenElement.h | 26 + .../xpath/XPathWildcardAnywhereElement.cpp | 23 + .../tree/xpath/XPathWildcardAnywhereElement.h | 23 + .../tree/xpath/XPathWildcardElement.cpp | 24 + .../tree/xpath/XPathWildcardElement.h | 23 + 308 files changed, 29835 insertions(+), 1 deletion(-) create mode 100644 CMakeLists.txt create mode 100644 third_party/antlr4-runtime/ANTLRErrorListener.cpp create mode 100755 third_party/antlr4-runtime/ANTLRErrorListener.h create mode 100644 third_party/antlr4-runtime/ANTLRErrorStrategy.cpp create mode 100755 third_party/antlr4-runtime/ANTLRErrorStrategy.h create mode 100755 third_party/antlr4-runtime/ANTLRFileStream.cpp create mode 100755 third_party/antlr4-runtime/ANTLRFileStream.h create mode 100755 third_party/antlr4-runtime/ANTLRInputStream.cpp create mode 100755 third_party/antlr4-runtime/ANTLRInputStream.h create mode 100755 third_party/antlr4-runtime/BailErrorStrategy.cpp create mode 100755 third_party/antlr4-runtime/BailErrorStrategy.h create mode 100755 third_party/antlr4-runtime/BaseErrorListener.cpp create mode 100755 third_party/antlr4-runtime/BaseErrorListener.h create mode 100755 third_party/antlr4-runtime/BufferedTokenStream.cpp create mode 100755 third_party/antlr4-runtime/BufferedTokenStream.h create mode 100755 third_party/antlr4-runtime/CharStream.cpp create mode 100755 third_party/antlr4-runtime/CharStream.h create mode 100755 third_party/antlr4-runtime/CommonToken.cpp create mode 100755 third_party/antlr4-runtime/CommonToken.h create mode 100755 third_party/antlr4-runtime/CommonTokenFactory.cpp create mode 100755 third_party/antlr4-runtime/CommonTokenFactory.h create mode 100755 third_party/antlr4-runtime/CommonTokenStream.cpp create mode 100755 third_party/antlr4-runtime/CommonTokenStream.h create mode 100755 third_party/antlr4-runtime/ConsoleErrorListener.cpp create mode 100755 third_party/antlr4-runtime/ConsoleErrorListener.h create mode 100755 third_party/antlr4-runtime/DefaultErrorStrategy.cpp create mode 100755 third_party/antlr4-runtime/DefaultErrorStrategy.h create mode 100755 third_party/antlr4-runtime/DiagnosticErrorListener.cpp create mode 100755 third_party/antlr4-runtime/DiagnosticErrorListener.h create mode 100644 third_party/antlr4-runtime/Exceptions.cpp create mode 100644 third_party/antlr4-runtime/Exceptions.h create mode 100755 third_party/antlr4-runtime/FailedPredicateException.cpp create mode 100755 third_party/antlr4-runtime/FailedPredicateException.h create mode 100755 third_party/antlr4-runtime/InputMismatchException.cpp create mode 100755 third_party/antlr4-runtime/InputMismatchException.h create mode 100755 third_party/antlr4-runtime/IntStream.cpp create mode 100755 third_party/antlr4-runtime/IntStream.h create mode 100755 third_party/antlr4-runtime/InterpreterRuleContext.cpp create mode 100755 third_party/antlr4-runtime/InterpreterRuleContext.h create mode 100755 third_party/antlr4-runtime/Lexer.cpp create mode 100755 third_party/antlr4-runtime/Lexer.h create mode 100755 third_party/antlr4-runtime/LexerInterpreter.cpp create mode 100755 third_party/antlr4-runtime/LexerInterpreter.h create mode 100755 third_party/antlr4-runtime/LexerNoViableAltException.cpp create mode 100755 third_party/antlr4-runtime/LexerNoViableAltException.h create mode 100755 third_party/antlr4-runtime/ListTokenSource.cpp create mode 100755 third_party/antlr4-runtime/ListTokenSource.h create mode 100755 third_party/antlr4-runtime/NoViableAltException.cpp create mode 100755 third_party/antlr4-runtime/NoViableAltException.h create mode 100755 third_party/antlr4-runtime/Parser.cpp create mode 100755 third_party/antlr4-runtime/Parser.h create mode 100755 third_party/antlr4-runtime/ParserInterpreter.cpp create mode 100755 third_party/antlr4-runtime/ParserInterpreter.h create mode 100755 third_party/antlr4-runtime/ParserRuleContext.cpp create mode 100755 third_party/antlr4-runtime/ParserRuleContext.h create mode 100755 third_party/antlr4-runtime/ProxyErrorListener.cpp create mode 100755 third_party/antlr4-runtime/ProxyErrorListener.h create mode 100755 third_party/antlr4-runtime/RecognitionException.cpp create mode 100755 third_party/antlr4-runtime/RecognitionException.h create mode 100755 third_party/antlr4-runtime/Recognizer.cpp create mode 100755 third_party/antlr4-runtime/Recognizer.h create mode 100755 third_party/antlr4-runtime/RuleContext.cpp create mode 100755 third_party/antlr4-runtime/RuleContext.h create mode 100755 third_party/antlr4-runtime/RuleContextWithAltNum.cpp create mode 100755 third_party/antlr4-runtime/RuleContextWithAltNum.h create mode 100755 third_party/antlr4-runtime/RuntimeMetaData.cpp create mode 100755 third_party/antlr4-runtime/RuntimeMetaData.h create mode 100644 third_party/antlr4-runtime/Token.cpp create mode 100755 third_party/antlr4-runtime/Token.h create mode 100755 third_party/antlr4-runtime/TokenFactory.h create mode 100644 third_party/antlr4-runtime/TokenSource.cpp create mode 100755 third_party/antlr4-runtime/TokenSource.h create mode 100755 third_party/antlr4-runtime/TokenStream.cpp create mode 100755 third_party/antlr4-runtime/TokenStream.h create mode 100755 third_party/antlr4-runtime/TokenStreamRewriter.cpp create mode 100755 third_party/antlr4-runtime/TokenStreamRewriter.h create mode 100755 third_party/antlr4-runtime/UnbufferedCharStream.cpp create mode 100755 third_party/antlr4-runtime/UnbufferedCharStream.h create mode 100755 third_party/antlr4-runtime/UnbufferedTokenStream.cpp create mode 100755 third_party/antlr4-runtime/UnbufferedTokenStream.h create mode 100755 third_party/antlr4-runtime/Vocabulary.cpp create mode 100755 third_party/antlr4-runtime/Vocabulary.h create mode 100644 third_party/antlr4-runtime/WritableToken.cpp create mode 100755 third_party/antlr4-runtime/WritableToken.h create mode 100644 third_party/antlr4-runtime/antlr4-common.h create mode 100644 third_party/antlr4-runtime/antlr4-runtime.h create mode 100755 third_party/antlr4-runtime/atn/ATN.cpp create mode 100755 third_party/antlr4-runtime/atn/ATN.h create mode 100755 third_party/antlr4-runtime/atn/ATNConfig.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNConfig.h create mode 100755 third_party/antlr4-runtime/atn/ATNConfigSet.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNConfigSet.h create mode 100755 third_party/antlr4-runtime/atn/ATNDeserializationOptions.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNDeserializationOptions.h create mode 100755 third_party/antlr4-runtime/atn/ATNDeserializer.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNDeserializer.h create mode 100755 third_party/antlr4-runtime/atn/ATNSerializer.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNSerializer.h create mode 100755 third_party/antlr4-runtime/atn/ATNSimulator.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNSimulator.h create mode 100755 third_party/antlr4-runtime/atn/ATNState.cpp create mode 100755 third_party/antlr4-runtime/atn/ATNState.h create mode 100755 third_party/antlr4-runtime/atn/ATNType.h create mode 100755 third_party/antlr4-runtime/atn/AbstractPredicateTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/AbstractPredicateTransition.h create mode 100755 third_party/antlr4-runtime/atn/ActionTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/ActionTransition.h create mode 100755 third_party/antlr4-runtime/atn/AmbiguityInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/AmbiguityInfo.h create mode 100755 third_party/antlr4-runtime/atn/ArrayPredictionContext.cpp create mode 100755 third_party/antlr4-runtime/atn/ArrayPredictionContext.h create mode 100755 third_party/antlr4-runtime/atn/AtomTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/AtomTransition.h create mode 100755 third_party/antlr4-runtime/atn/BasicBlockStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/BasicBlockStartState.h create mode 100755 third_party/antlr4-runtime/atn/BasicState.cpp create mode 100755 third_party/antlr4-runtime/atn/BasicState.h create mode 100755 third_party/antlr4-runtime/atn/BlockEndState.cpp create mode 100755 third_party/antlr4-runtime/atn/BlockEndState.h create mode 100644 third_party/antlr4-runtime/atn/BlockStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/BlockStartState.h create mode 100755 third_party/antlr4-runtime/atn/ContextSensitivityInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/ContextSensitivityInfo.h create mode 100755 third_party/antlr4-runtime/atn/DecisionEventInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/DecisionEventInfo.h create mode 100755 third_party/antlr4-runtime/atn/DecisionInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/DecisionInfo.h create mode 100755 third_party/antlr4-runtime/atn/DecisionState.cpp create mode 100755 third_party/antlr4-runtime/atn/DecisionState.h create mode 100755 third_party/antlr4-runtime/atn/EmptyPredictionContext.cpp create mode 100755 third_party/antlr4-runtime/atn/EmptyPredictionContext.h create mode 100755 third_party/antlr4-runtime/atn/EpsilonTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/EpsilonTransition.h create mode 100755 third_party/antlr4-runtime/atn/ErrorInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/ErrorInfo.h create mode 100755 third_party/antlr4-runtime/atn/LL1Analyzer.cpp create mode 100755 third_party/antlr4-runtime/atn/LL1Analyzer.h create mode 100755 third_party/antlr4-runtime/atn/LexerATNConfig.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerATNConfig.h create mode 100755 third_party/antlr4-runtime/atn/LexerATNSimulator.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerATNSimulator.h create mode 100644 third_party/antlr4-runtime/atn/LexerAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerActionExecutor.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerActionExecutor.h create mode 100755 third_party/antlr4-runtime/atn/LexerActionType.h create mode 100755 third_party/antlr4-runtime/atn/LexerChannelAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerChannelAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerCustomAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerCustomAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerIndexedCustomAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerIndexedCustomAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerModeAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerModeAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerMoreAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerMoreAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerPopModeAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerPopModeAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerPushModeAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerPushModeAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerSkipAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerSkipAction.h create mode 100755 third_party/antlr4-runtime/atn/LexerTypeAction.cpp create mode 100755 third_party/antlr4-runtime/atn/LexerTypeAction.h create mode 100755 third_party/antlr4-runtime/atn/LookaheadEventInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/LookaheadEventInfo.h create mode 100755 third_party/antlr4-runtime/atn/LoopEndState.cpp create mode 100755 third_party/antlr4-runtime/atn/LoopEndState.h create mode 100755 third_party/antlr4-runtime/atn/NotSetTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/NotSetTransition.h create mode 100755 third_party/antlr4-runtime/atn/OrderedATNConfigSet.cpp create mode 100755 third_party/antlr4-runtime/atn/OrderedATNConfigSet.h create mode 100755 third_party/antlr4-runtime/atn/ParseInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/ParseInfo.h create mode 100755 third_party/antlr4-runtime/atn/ParserATNSimulator.cpp create mode 100755 third_party/antlr4-runtime/atn/ParserATNSimulator.h create mode 100755 third_party/antlr4-runtime/atn/PlusBlockStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/PlusBlockStartState.h create mode 100755 third_party/antlr4-runtime/atn/PlusLoopbackState.cpp create mode 100755 third_party/antlr4-runtime/atn/PlusLoopbackState.h create mode 100755 third_party/antlr4-runtime/atn/PrecedencePredicateTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/PrecedencePredicateTransition.h create mode 100755 third_party/antlr4-runtime/atn/PredicateEvalInfo.cpp create mode 100755 third_party/antlr4-runtime/atn/PredicateEvalInfo.h create mode 100755 third_party/antlr4-runtime/atn/PredicateTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/PredicateTransition.h create mode 100755 third_party/antlr4-runtime/atn/PredictionContext.cpp create mode 100755 third_party/antlr4-runtime/atn/PredictionContext.h create mode 100755 third_party/antlr4-runtime/atn/PredictionMode.cpp create mode 100755 third_party/antlr4-runtime/atn/PredictionMode.h create mode 100755 third_party/antlr4-runtime/atn/ProfilingATNSimulator.cpp create mode 100755 third_party/antlr4-runtime/atn/ProfilingATNSimulator.h create mode 100755 third_party/antlr4-runtime/atn/RangeTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/RangeTransition.h create mode 100755 third_party/antlr4-runtime/atn/RuleStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/RuleStartState.h create mode 100755 third_party/antlr4-runtime/atn/RuleStopState.cpp create mode 100755 third_party/antlr4-runtime/atn/RuleStopState.h create mode 100755 third_party/antlr4-runtime/atn/RuleTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/RuleTransition.h create mode 100755 third_party/antlr4-runtime/atn/SemanticContext.cpp create mode 100755 third_party/antlr4-runtime/atn/SemanticContext.h create mode 100755 third_party/antlr4-runtime/atn/SetTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/SetTransition.h create mode 100755 third_party/antlr4-runtime/atn/SingletonPredictionContext.cpp create mode 100755 third_party/antlr4-runtime/atn/SingletonPredictionContext.h create mode 100755 third_party/antlr4-runtime/atn/StarBlockStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/StarBlockStartState.h create mode 100755 third_party/antlr4-runtime/atn/StarLoopEntryState.cpp create mode 100755 third_party/antlr4-runtime/atn/StarLoopEntryState.h create mode 100755 third_party/antlr4-runtime/atn/StarLoopbackState.cpp create mode 100755 third_party/antlr4-runtime/atn/StarLoopbackState.h create mode 100755 third_party/antlr4-runtime/atn/TokensStartState.cpp create mode 100755 third_party/antlr4-runtime/atn/TokensStartState.h create mode 100755 third_party/antlr4-runtime/atn/Transition.cpp create mode 100755 third_party/antlr4-runtime/atn/Transition.h create mode 100755 third_party/antlr4-runtime/atn/WildcardTransition.cpp create mode 100755 third_party/antlr4-runtime/atn/WildcardTransition.h create mode 100755 third_party/antlr4-runtime/dfa/DFA.cpp create mode 100755 third_party/antlr4-runtime/dfa/DFA.h create mode 100755 third_party/antlr4-runtime/dfa/DFASerializer.cpp create mode 100755 third_party/antlr4-runtime/dfa/DFASerializer.h create mode 100755 third_party/antlr4-runtime/dfa/DFAState.cpp create mode 100755 third_party/antlr4-runtime/dfa/DFAState.h create mode 100755 third_party/antlr4-runtime/dfa/LexerDFASerializer.cpp create mode 100755 third_party/antlr4-runtime/dfa/LexerDFASerializer.h create mode 100755 third_party/antlr4-runtime/misc/InterpreterDataReader.cpp create mode 100755 third_party/antlr4-runtime/misc/InterpreterDataReader.h create mode 100755 third_party/antlr4-runtime/misc/Interval.cpp create mode 100755 third_party/antlr4-runtime/misc/Interval.h create mode 100755 third_party/antlr4-runtime/misc/IntervalSet.cpp create mode 100755 third_party/antlr4-runtime/misc/IntervalSet.h create mode 100755 third_party/antlr4-runtime/misc/MurmurHash.cpp create mode 100755 third_party/antlr4-runtime/misc/MurmurHash.h create mode 100644 third_party/antlr4-runtime/misc/Predicate.cpp create mode 100755 third_party/antlr4-runtime/misc/Predicate.h create mode 100644 third_party/antlr4-runtime/support/Any.cpp create mode 100644 third_party/antlr4-runtime/support/Any.h create mode 100644 third_party/antlr4-runtime/support/Arrays.cpp create mode 100644 third_party/antlr4-runtime/support/Arrays.h create mode 100644 third_party/antlr4-runtime/support/BitSet.h create mode 100755 third_party/antlr4-runtime/support/CPPUtils.cpp create mode 100644 third_party/antlr4-runtime/support/CPPUtils.h create mode 100644 third_party/antlr4-runtime/support/Declarations.h create mode 100644 third_party/antlr4-runtime/support/StringUtils.cpp create mode 100644 third_party/antlr4-runtime/support/StringUtils.h create mode 100755 third_party/antlr4-runtime/support/guid.cpp create mode 100755 third_party/antlr4-runtime/support/guid.h create mode 100755 third_party/antlr4-runtime/tree/AbstractParseTreeVisitor.h create mode 100644 third_party/antlr4-runtime/tree/ErrorNode.cpp create mode 100755 third_party/antlr4-runtime/tree/ErrorNode.h create mode 100755 third_party/antlr4-runtime/tree/ErrorNodeImpl.cpp create mode 100755 third_party/antlr4-runtime/tree/ErrorNodeImpl.h create mode 100644 third_party/antlr4-runtime/tree/IterativeParseTreeWalker.cpp create mode 100644 third_party/antlr4-runtime/tree/IterativeParseTreeWalker.h create mode 100755 third_party/antlr4-runtime/tree/ParseTree.cpp create mode 100755 third_party/antlr4-runtime/tree/ParseTree.h create mode 100644 third_party/antlr4-runtime/tree/ParseTreeListener.cpp create mode 100755 third_party/antlr4-runtime/tree/ParseTreeListener.h create mode 100755 third_party/antlr4-runtime/tree/ParseTreeProperty.h create mode 100644 third_party/antlr4-runtime/tree/ParseTreeVisitor.cpp create mode 100755 third_party/antlr4-runtime/tree/ParseTreeVisitor.h create mode 100755 third_party/antlr4-runtime/tree/ParseTreeWalker.cpp create mode 100755 third_party/antlr4-runtime/tree/ParseTreeWalker.h create mode 100644 third_party/antlr4-runtime/tree/TerminalNode.cpp create mode 100755 third_party/antlr4-runtime/tree/TerminalNode.h create mode 100755 third_party/antlr4-runtime/tree/TerminalNodeImpl.cpp create mode 100755 third_party/antlr4-runtime/tree/TerminalNodeImpl.h create mode 100755 third_party/antlr4-runtime/tree/Trees.cpp create mode 100755 third_party/antlr4-runtime/tree/Trees.h create mode 100644 third_party/antlr4-runtime/tree/pattern/Chunk.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/Chunk.h create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreeMatch.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreeMatch.h create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreePattern.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreePattern.h create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreePatternMatcher.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/ParseTreePatternMatcher.h create mode 100755 third_party/antlr4-runtime/tree/pattern/RuleTagToken.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/RuleTagToken.h create mode 100755 third_party/antlr4-runtime/tree/pattern/TagChunk.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/TagChunk.h create mode 100755 third_party/antlr4-runtime/tree/pattern/TextChunk.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/TextChunk.h create mode 100755 third_party/antlr4-runtime/tree/pattern/TokenTagToken.cpp create mode 100755 third_party/antlr4-runtime/tree/pattern/TokenTagToken.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPath.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPath.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathElement.h create mode 100644 third_party/antlr4-runtime/tree/xpath/XPathLexer.cpp create mode 100644 third_party/antlr4-runtime/tree/xpath/XPathLexer.g4 create mode 100644 third_party/antlr4-runtime/tree/xpath/XPathLexer.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathLexerErrorListener.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathLexerErrorListener.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathRuleAnywhereElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathRuleAnywhereElement.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathRuleElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathRuleElement.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathTokenAnywhereElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathTokenAnywhereElement.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathTokenElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathTokenElement.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathWildcardAnywhereElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathWildcardAnywhereElement.h create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathWildcardElement.cpp create mode 100755 third_party/antlr4-runtime/tree/xpath/XPathWildcardElement.h diff --git a/.gitignore b/.gitignore index d5ec827..90e7a4c 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,4 @@ +## RUST IGNORE Cargo.lock target test/out @@ -8,4 +9,62 @@ test/out .idea *.S *.s -a.out \ No newline at end of file +a.out +**/.DS_Store +./vscode/** + +## CPP IGNORE +# Prerequisites +*.d + +# Compiled Object files +*.slo +*.lo +*.o +*.obj + +# Precompiled Headers +*.gch +*.pch + +# Compiled Dynamic libraries +*.so +*.dylib +*.dll + +# Fortran module files +*.mod +*.smod + +# Compiled Static libraries +*.lai +*.la +*.a +*.lib + +# Executables +*.exe +*.out +*.app + +## CMAKE IGNORE +build +CMakeLists.txt.user +CMakeCache.txt +CMakeFiles +CMakeScripts +Testing +Makefile +cmake_install.cmake +install_manifest.txt +compile_commands.json +CTestTestfile.cmake +_deps + +## ANTLR IGNORE +generated +!MiniDecaf.g4 +*.tokens +*.interp + +a.out diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..d88d305 --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,55 @@ +cmake_minimum_required(VERSION 3.10) +project(MiniDecaf) + +set(CMAKE_CXX_STANDARD 11) +set(CMAKE_CXX_STANDARD_REQUIRED True) + +include_directories( + ${PROJECT_SOURCE_DIR}/generated/ + ${PROJECT_SOURCE_DIR}/third_party/ + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/ + ${PROJECT_SOURCE_DIR}/src/ +) + +set(src_dir + ${PROJECT_SOURCE_DIR}/generated/MiniDecafLexer.cpp + ${PROJECT_SOURCE_DIR}/generated/MiniDecafParser.cpp + ${PROJECT_SOURCE_DIR}/generated/MiniDecafVisitor.cpp + ${PROJECT_SOURCE_DIR}/generated/MiniDecafBaseVisitor.cpp + ${PROJECT_SOURCE_DIR}/src/CodeGenVisitor.cpp + ${PROJECT_SOURCE_DIR}/src/VarAllocVisitor.cpp +) + +file(GLOB antlr4-cpp-src + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/atn/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/dfa/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/misc/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/support/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/tree/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/tree/pattern/*.cpp + ${PROJECT_SOURCE_DIR}/third_party/antlr4-runtime/tree/xpath/*.cpp +) + +add_library(antlr4-cpp-runtime ${antlr4-cpp-src}) +add_executable(MiniDecaf ${src_dir} src/main.cpp) +target_link_libraries(MiniDecaf antlr4-cpp-runtime) + +# add_custom_command(TARGET antlr4-cpp-runtime +# PRE_BUILD +# WORKING_DIRECTORY +# ${PROJECT_SOURCE_DIR}/generated/ +# COMMAND +# java -jar /usr/local/lib/antlr-4.8-complete.jar -Dlanguage=Cpp -no-listener -visitor MiniDecaf.g4 +# COMMENT +# "Auto updates for developing antlr grammar" +# ) + +add_custom_target(update_antlr + WORKING_DIRECTORY + ${PROJECT_SOURCE_DIR}/generated/ + COMMAND + java -jar /usr/local/lib/antlr-4.8-complete.jar -Dlanguage=Cpp -no-listener -visitor MiniDecaf.g4 + COMMENT + "Auto updates for developing antlr grammar" +) diff --git a/third_party/antlr4-runtime/ANTLRErrorListener.cpp b/third_party/antlr4-runtime/ANTLRErrorListener.cpp new file mode 100644 index 0000000..6ceadb8 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRErrorListener.cpp @@ -0,0 +1,10 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "ANTLRErrorListener.h" + +antlr4::ANTLRErrorListener::~ANTLRErrorListener() +{ +} diff --git a/third_party/antlr4-runtime/ANTLRErrorListener.h b/third_party/antlr4-runtime/ANTLRErrorListener.h new file mode 100755 index 0000000..d6efad1 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRErrorListener.h @@ -0,0 +1,167 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "RecognitionException.h" + +namespace antlrcpp { + class BitSet; +} + +namespace antlr4 { + + /// How to emit recognition errors (an interface in Java). + class ANTLR4CPP_PUBLIC ANTLRErrorListener { + public: + virtual ~ANTLRErrorListener(); + + /// + /// Upon syntax error, notify any interested parties. This is not how to + /// recover from errors or compute error messages. + /// specifies how to recover from syntax errors and how to compute error + /// messages. This listener's job is simply to emit a computed message, + /// though it has enough information to create its own message in many cases. + ///

+ /// The is non-null for all syntax errors except + /// when we discover mismatched token errors that we can recover from + /// in-line, without returning from the surrounding rule (via the single + /// token insertion and deletion mechanism). + ///

+ /// + /// What parser got the error. From this + /// object, you can access the context as well + /// as the input stream. + /// + /// The offending token in the input token + /// stream, unless recognizer is a lexer (then it's null). If + /// no viable alternative error, {@code e} has token at which we + /// started production for the decision. + /// + /// The line number in the input where the error occurred. + /// + /// The character position within that line where the error occurred. + /// + /// The message to emit. + /// + /// The exception generated by the parser that led to + /// the reporting of an error. It is null in the case where + /// the parser was able to recover in line without exiting the + /// surrounding rule. + virtual void syntaxError(Recognizer *recognizer, Token *offendingSymbol, size_t line, + size_t charPositionInLine, const std::string &msg, std::exception_ptr e) = 0; + + /** + * This method is called by the parser when a full-context prediction + * results in an ambiguity. + * + *

Each full-context prediction which does not result in a syntax error + * will call either {@link #reportContextSensitivity} or + * {@link #reportAmbiguity}.

+ * + *

When {@code ambigAlts} is not null, it contains the set of potentially + * viable alternatives identified by the prediction algorithm. When + * {@code ambigAlts} is null, use {@link ATNConfigSet#getAlts} to obtain the + * represented alternatives from the {@code configs} argument.

+ * + *

When {@code exact} is {@code true}, all of the potentially + * viable alternatives are truly viable, i.e. this is reporting an exact + * ambiguity. When {@code exact} is {@code false}, at least two of + * the potentially viable alternatives are viable for the current input, but + * the prediction algorithm terminated as soon as it determined that at + * least the minimum potentially viable alternative is truly + * viable.

+ * + *

When the {@link PredictionMode#LL_EXACT_AMBIG_DETECTION} prediction + * mode is used, the parser is required to identify exact ambiguities so + * {@code exact} will always be {@code true}.

+ * + *

This method is not used by lexers.

+ * + * @param recognizer the parser instance + * @param dfa the DFA for the current decision + * @param startIndex the input index where the decision started + * @param stopIndex the input input where the ambiguity was identified + * @param exact {@code true} if the ambiguity is exactly known, otherwise + * {@code false}. This is always {@code true} when + * {@link PredictionMode#LL_EXACT_AMBIG_DETECTION} is used. + * @param ambigAlts the potentially ambiguous alternatives, or {@code null} + * to indicate that the potentially ambiguous alternatives are the complete + * set of represented alternatives in {@code configs} + * @param configs the ATN configuration set where the ambiguity was + * identified + */ + virtual void reportAmbiguity(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, bool exact, + const antlrcpp::BitSet &ambigAlts, atn::ATNConfigSet *configs) = 0; + + /** + * This method is called when an SLL conflict occurs and the parser is about + * to use the full context information to make an LL decision. + * + *

If one or more configurations in {@code configs} contains a semantic + * predicate, the predicates are evaluated before this method is called. The + * subset of alternatives which are still viable after predicates are + * evaluated is reported in {@code conflictingAlts}.

+ * + *

This method is not used by lexers.

+ * + * @param recognizer the parser instance + * @param dfa the DFA for the current decision + * @param startIndex the input index where the decision started + * @param stopIndex the input index where the SLL conflict occurred + * @param conflictingAlts The specific conflicting alternatives. If this is + * {@code null}, the conflicting alternatives are all alternatives + * represented in {@code configs}. At the moment, conflictingAlts is non-null + * (for the reference implementation, but Sam's optimized version can see this + * as null). + * @param configs the ATN configuration set where the SLL conflict was + * detected + */ + virtual void reportAttemptingFullContext(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, + const antlrcpp::BitSet &conflictingAlts, atn::ATNConfigSet *configs) = 0; + + /** + * This method is called by the parser when a full-context prediction has a + * unique result. + * + *

Each full-context prediction which does not result in a syntax error + * will call either {@link #reportContextSensitivity} or + * {@link #reportAmbiguity}.

+ * + *

For prediction implementations that only evaluate full-context + * predictions when an SLL conflict is found (including the default + * {@link ParserATNSimulator} implementation), this method reports cases + * where SLL conflicts were resolved to unique full-context predictions, + * i.e. the decision was context-sensitive. This report does not necessarily + * indicate a problem, and it may appear even in completely unambiguous + * grammars.

+ * + *

{@code configs} may have more than one represented alternative if the + * full-context prediction algorithm does not evaluate predicates before + * beginning the full-context prediction. In all cases, the final prediction + * is passed as the {@code prediction} argument.

+ * + *

Note that the definition of "context sensitivity" in this method + * differs from the concept in {@link DecisionInfo#contextSensitivities}. + * This method reports all instances where an SLL conflict occurred but LL + * parsing produced a unique result, whether or not that unique result + * matches the minimum alternative in the SLL conflicting set.

+ * + *

This method is not used by lexers.

+ * + * @param recognizer the parser instance + * @param dfa the DFA for the current decision + * @param startIndex the input index where the decision started + * @param stopIndex the input index where the context sensitivity was + * finally determined + * @param prediction the unambiguous result of the full-context prediction + * @param configs the ATN configuration set where the unambiguous prediction + * was determined + */ + virtual void reportContextSensitivity(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, + size_t prediction, atn::ATNConfigSet *configs) = 0; + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/ANTLRErrorStrategy.cpp b/third_party/antlr4-runtime/ANTLRErrorStrategy.cpp new file mode 100644 index 0000000..1655a57 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRErrorStrategy.cpp @@ -0,0 +1,10 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "ANTLRErrorStrategy.h" + +antlr4::ANTLRErrorStrategy::~ANTLRErrorStrategy() +{ +} diff --git a/third_party/antlr4-runtime/ANTLRErrorStrategy.h b/third_party/antlr4-runtime/ANTLRErrorStrategy.h new file mode 100755 index 0000000..a3eecd1 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRErrorStrategy.h @@ -0,0 +1,121 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "Token.h" + +namespace antlr4 { + + /// + /// The interface for defining strategies to deal with syntax errors encountered + /// during a parse by ANTLR-generated parsers. We distinguish between three + /// different kinds of errors: + /// + ///
    + ///
  • The parser could not figure out which path to take in the ATN (none of + /// the available alternatives could possibly match)
    • + ///
  • The current input does not match what we were looking for
    • + ///
  • A predicate evaluated to false
    • + ///
+ /// + /// Implementations of this interface report syntax errors by calling + /// . + ///

+ /// TODO: what to do about lexers + ///

+ class ANTLR4CPP_PUBLIC ANTLRErrorStrategy { + public: + + /// + /// Reset the error handler state for the specified {@code recognizer}. + /// the parser instance + virtual ~ANTLRErrorStrategy(); + + virtual void reset(Parser *recognizer) = 0; + + /** + * This method is called when an unexpected symbol is encountered during an + * inline match operation, such as {@link Parser#match}. If the error + * strategy successfully recovers from the match failure, this method + * returns the {@link Token} instance which should be treated as the + * successful result of the match. + * + *

This method handles the consumption of any tokens - the caller should + * not call {@link Parser#consume} after a successful recovery.

+ * + *

Note that the calling code will not report an error if this method + * returns successfully. The error strategy implementation is responsible + * for calling {@link Parser#notifyErrorListeners} as appropriate.

+ * + * @param recognizer the parser instance + * @throws RecognitionException if the error strategy was not able to + * recover from the unexpected input symbol + */ + virtual Token* recoverInline(Parser *recognizer) = 0; + + /// + /// This method is called to recover from exception {@code e}. This method is + /// called after by the default exception handler + /// generated for a rule method. + /// + /// + /// the parser instance + /// the recognition exception to recover from + /// if the error strategy could not recover from + /// the recognition exception + virtual void recover(Parser *recognizer, std::exception_ptr e) = 0; + + /// + /// This method provides the error handler with an opportunity to handle + /// syntactic or semantic errors in the input stream before they result in a + /// . + ///

+ /// The generated code currently contains calls to after + /// entering the decision state of a closure block ({@code (...)*} or + /// {@code (...)+}). + ///

+ /// For an implementation based on Jim Idle's "magic sync" mechanism, see + /// . + ///

+ /// + /// the parser instance + /// if an error is detected by the error + /// strategy but cannot be automatically recovered at the current state in + /// the parsing process + virtual void sync(Parser *recognizer) = 0; + + /// + /// Tests whether or not {@code recognizer} is in the process of recovering + /// from an error. In error recovery mode, adds + /// symbols to the parse tree by calling + /// {@link Parser#createErrorNode(ParserRuleContext, Token)} then + /// {@link ParserRuleContext#addErrorNode(ErrorNode)} instead of + /// {@link Parser#createTerminalNode(ParserRuleContext, Token)}. + /// + /// the parser instance + /// {@code true} if the parser is currently recovering from a parse + /// error, otherwise {@code false} + virtual bool inErrorRecoveryMode(Parser *recognizer) = 0; + + /// + /// This method is called by when the parser successfully matches an input + /// symbol. + /// + /// the parser instance + virtual void reportMatch(Parser *recognizer) = 0; + + /// + /// Report any kind of . This method is called by + /// the default exception handler generated for a rule method. + /// + /// the parser instance + /// the recognition exception to report + virtual void reportError(Parser *recognizer, const RecognitionException &e) = 0; + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/ANTLRFileStream.cpp b/third_party/antlr4-runtime/ANTLRFileStream.cpp new file mode 100755 index 0000000..64b0b11 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRFileStream.cpp @@ -0,0 +1,34 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "support/StringUtils.h" + +#include "ANTLRFileStream.h" + +using namespace antlr4; + +ANTLRFileStream::ANTLRFileStream(const std::string &fileName) { + _fileName = fileName; + loadFromFile(fileName); +} + +void ANTLRFileStream::loadFromFile(const std::string &fileName) { + _fileName = fileName; + if (_fileName.empty()) { + return; + } + +#ifdef _MSC_VER + std::ifstream stream(antlrcpp::s2ws(fileName), std::ios::binary); +#else + std::ifstream stream(fileName, std::ios::binary); +#endif + + ANTLRInputStream::load(stream); +} + +std::string ANTLRFileStream::getSourceName() const { + return _fileName; +} diff --git a/third_party/antlr4-runtime/ANTLRFileStream.h b/third_party/antlr4-runtime/ANTLRFileStream.h new file mode 100755 index 0000000..10c8550 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRFileStream.h @@ -0,0 +1,27 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "ANTLRInputStream.h" + +namespace antlr4 { + + /// This is an ANTLRInputStream that is loaded from a file all at once + /// when you construct the object (or call load()). + // TODO: this class needs testing. + class ANTLR4CPP_PUBLIC ANTLRFileStream : public ANTLRInputStream { + protected: + std::string _fileName; // UTF-8 encoded file name. + + public: + // Assumes a file name encoded in UTF-8 and file content in the same encoding (with or w/o BOM). + ANTLRFileStream(const std::string &fileName); + + virtual void loadFromFile(const std::string &fileName); + virtual std::string getSourceName() const override; + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/ANTLRInputStream.cpp b/third_party/antlr4-runtime/ANTLRInputStream.cpp new file mode 100755 index 0000000..a5e2161 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRInputStream.cpp @@ -0,0 +1,155 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "Exceptions.h" +#include "misc/Interval.h" +#include "IntStream.h" + +#include "support/StringUtils.h" +#include "support/CPPUtils.h" + +#include "ANTLRInputStream.h" + +using namespace antlr4; +using namespace antlrcpp; + +using misc::Interval; + +ANTLRInputStream::ANTLRInputStream(const std::string &input) { + InitializeInstanceFields(); + load(input); +} + +ANTLRInputStream::ANTLRInputStream(const char data_[], size_t numberOfActualCharsInArray) + : ANTLRInputStream(std::string(data_, numberOfActualCharsInArray)) { +} + +ANTLRInputStream::ANTLRInputStream(std::istream &stream) { + InitializeInstanceFields(); + load(stream); +} + +void ANTLRInputStream::load(const std::string &input) { + // Remove the UTF-8 BOM if present. + const char bom[4] = "\xef\xbb\xbf"; + if (input.compare(0, 3, bom, 3) == 0) + _data = antlrcpp::utf8_to_utf32(input.data() + 3, input.data() + input.size()); + else + _data = antlrcpp::utf8_to_utf32(input.data(), input.data() + input.size()); + p = 0; +} + +void ANTLRInputStream::load(std::istream &stream) { + if (!stream.good() || stream.eof()) // No fail, bad or EOF. + return; + + _data.clear(); + + std::string s((std::istreambuf_iterator(stream)), std::istreambuf_iterator()); + load(s); +} + +void ANTLRInputStream::reset() { + p = 0; +} + +void ANTLRInputStream::consume() { + if (p >= _data.size()) { + assert(LA(1) == IntStream::EOF); + throw IllegalStateException("cannot consume EOF"); + } + + if (p < _data.size()) { + p++; + } +} + +size_t ANTLRInputStream::LA(ssize_t i) { + if (i == 0) { + return 0; // undefined + } + + ssize_t position = static_cast(p); + if (i < 0) { + i++; // e.g., translate LA(-1) to use offset i=0; then _data[p+0-1] + if ((position + i - 1) < 0) { + return IntStream::EOF; // invalid; no char before first char + } + } + + if ((position + i - 1) >= static_cast(_data.size())) { + return IntStream::EOF; + } + + return _data[static_cast((position + i - 1))]; +} + +size_t ANTLRInputStream::LT(ssize_t i) { + return LA(i); +} + +size_t ANTLRInputStream::index() { + return p; +} + +size_t ANTLRInputStream::size() { + return _data.size(); +} + +// Mark/release do nothing. We have entire buffer. +ssize_t ANTLRInputStream::mark() { + return -1; +} + +void ANTLRInputStream::release(ssize_t /* marker */) { +} + +void ANTLRInputStream::seek(size_t index) { + if (index <= p) { + p = index; // just jump; don't update stream state (line, ...) + return; + } + // seek forward, consume until p hits index or n (whichever comes first) + index = std::min(index, _data.size()); + while (p < index) { + consume(); + } +} + +std::string ANTLRInputStream::getText(const Interval &interval) { + if (interval.a < 0 || interval.b < 0) { + return ""; + } + + size_t start = static_cast(interval.a); + size_t stop = static_cast(interval.b); + + + if (stop >= _data.size()) { + stop = _data.size() - 1; + } + + size_t count = stop - start + 1; + if (start >= _data.size()) { + return ""; + } + + return antlrcpp::utf32_to_utf8(_data.substr(start, count)); +} + +std::string ANTLRInputStream::getSourceName() const { + if (name.empty()) { + return IntStream::UNKNOWN_SOURCE_NAME; + } + return name; +} + +std::string ANTLRInputStream::toString() const { + return antlrcpp::utf32_to_utf8(_data); +} + +void ANTLRInputStream::InitializeInstanceFields() { + p = 0; +} diff --git a/third_party/antlr4-runtime/ANTLRInputStream.h b/third_party/antlr4-runtime/ANTLRInputStream.h new file mode 100755 index 0000000..e985050 --- /dev/null +++ b/third_party/antlr4-runtime/ANTLRInputStream.h @@ -0,0 +1,69 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "CharStream.h" + +namespace antlr4 { + + // Vacuum all input from a stream and then treat it + // like a string. Can also pass in a string or char[] to use. + // Input is expected to be encoded in UTF-8 and converted to UTF-32 internally. + class ANTLR4CPP_PUBLIC ANTLRInputStream : public CharStream { + protected: + /// The data being scanned. + // UTF-32 + UTF32String _data; + + /// 0..n-1 index into string of next char + size_t p; + + public: + /// What is name or source of this char stream? + std::string name; + + ANTLRInputStream(const std::string &input = ""); + ANTLRInputStream(const char data_[], size_t numberOfActualCharsInArray); + ANTLRInputStream(std::istream &stream); + + virtual void load(const std::string &input); + virtual void load(std::istream &stream); + + /// Reset the stream so that it's in the same state it was + /// when the object was created *except* the data array is not + /// touched. + virtual void reset(); + virtual void consume() override; + virtual size_t LA(ssize_t i) override; + virtual size_t LT(ssize_t i); + + /// + /// Return the current input symbol index 0..n where n indicates the + /// last symbol has been read. The index is the index of char to + /// be returned from LA(1). + /// + virtual size_t index() override; + virtual size_t size() override; + + /// + /// mark/release do nothing; we have entire buffer + virtual ssize_t mark() override; + virtual void release(ssize_t marker) override; + + /// + /// consume() ahead until p==index; can't just set p=index as we must + /// update line and charPositionInLine. If we seek backwards, just set p + /// + virtual void seek(size_t index) override; + virtual std::string getText(const misc::Interval &interval) override; + virtual std::string getSourceName() const override; + virtual std::string toString() const override; + + private: + void InitializeInstanceFields(); + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/BailErrorStrategy.cpp b/third_party/antlr4-runtime/BailErrorStrategy.cpp new file mode 100755 index 0000000..5fbc011 --- /dev/null +++ b/third_party/antlr4-runtime/BailErrorStrategy.cpp @@ -0,0 +1,61 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "Exceptions.h" +#include "ParserRuleContext.h" +#include "InputMismatchException.h" +#include "Parser.h" + +#include "BailErrorStrategy.h" + +using namespace antlr4; + +void BailErrorStrategy::recover(Parser *recognizer, std::exception_ptr e) { + ParserRuleContext *context = recognizer->getContext(); + do { + context->exception = e; + if (context->parent == nullptr) + break; + context = static_cast(context->parent); + } while (true); + + try { + std::rethrow_exception(e); // Throw the exception to be able to catch and rethrow nested. +#if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026 + } catch (RecognitionException &inner) { + throw ParseCancellationException(inner.what()); +#else + } catch (RecognitionException & /*inner*/) { + std::throw_with_nested(ParseCancellationException()); +#endif + } +} + +Token* BailErrorStrategy::recoverInline(Parser *recognizer) { + InputMismatchException e(recognizer); + std::exception_ptr exception = std::make_exception_ptr(e); + + ParserRuleContext *context = recognizer->getContext(); + do { + context->exception = exception; + if (context->parent == nullptr) + break; + context = static_cast(context->parent); + } while (true); + + try { + throw e; +#if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026 + } catch (InputMismatchException &inner) { + throw ParseCancellationException(inner.what()); +#else + } catch (InputMismatchException & /*inner*/) { + std::throw_with_nested(ParseCancellationException()); +#endif + } +} + +void BailErrorStrategy::sync(Parser * /*recognizer*/) { +} diff --git a/third_party/antlr4-runtime/BailErrorStrategy.h b/third_party/antlr4-runtime/BailErrorStrategy.h new file mode 100755 index 0000000..2a8c36f --- /dev/null +++ b/third_party/antlr4-runtime/BailErrorStrategy.h @@ -0,0 +1,59 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "DefaultErrorStrategy.h" + +namespace antlr4 { + + /** + * This implementation of {@link ANTLRErrorStrategy} responds to syntax errors + * by immediately canceling the parse operation with a + * {@link ParseCancellationException}. The implementation ensures that the + * {@link ParserRuleContext#exception} field is set for all parse tree nodes + * that were not completed prior to encountering the error. + * + *

+ * This error strategy is useful in the following scenarios.

+ * + *
    + *
  • Two-stage parsing: This error strategy allows the first + * stage of two-stage parsing to immediately terminate if an error is + * encountered, and immediately fall back to the second stage. In addition to + * avoiding wasted work by attempting to recover from errors here, the empty + * implementation of {@link BailErrorStrategy#sync} improves the performance of + * the first stage.
    • + *
  • Silent validation: When syntax errors are not being + * reported or logged, and the parse result is simply ignored if errors occur, + * the {@link BailErrorStrategy} avoids wasting work on recovering from errors + * when the result will be ignored either way.
    • + *
+ * + *

+ * {@code myparser.setErrorHandler(new BailErrorStrategy());}

+ * + * @see Parser#setErrorHandler(ANTLRErrorStrategy) + */ + class ANTLR4CPP_PUBLIC BailErrorStrategy : public DefaultErrorStrategy { + /// + /// Instead of recovering from exception {@code e}, re-throw it wrapped + /// in a so it is not caught by the + /// rule function catches. Use to get the + /// original . + /// + public: + virtual void recover(Parser *recognizer, std::exception_ptr e) override; + + /// Make sure we don't attempt to recover inline; if the parser + /// successfully recovers, it won't throw an exception. + virtual Token* recoverInline(Parser *recognizer) override; + + /// + /// Make sure we don't attempt to recover from problems in subrules. + virtual void sync(Parser *recognizer) override; + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/BaseErrorListener.cpp b/third_party/antlr4-runtime/BaseErrorListener.cpp new file mode 100755 index 0000000..c035f09 --- /dev/null +++ b/third_party/antlr4-runtime/BaseErrorListener.cpp @@ -0,0 +1,25 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "BaseErrorListener.h" +#include "RecognitionException.h" + +using namespace antlr4; + +void BaseErrorListener::syntaxError(Recognizer * /*recognizer*/, Token * /*offendingSymbol*/, size_t /*line*/, + size_t /*charPositionInLine*/, const std::string &/*msg*/, std::exception_ptr /*e*/) { +} + +void BaseErrorListener::reportAmbiguity(Parser * /*recognizer*/, const dfa::DFA &/*dfa*/, size_t /*startIndex*/, + size_t /*stopIndex*/, bool /*exact*/, const antlrcpp::BitSet &/*ambigAlts*/, atn::ATNConfigSet * /*configs*/) { +} + +void BaseErrorListener::reportAttemptingFullContext(Parser * /*recognizer*/, const dfa::DFA &/*dfa*/, size_t /*startIndex*/, + size_t /*stopIndex*/, const antlrcpp::BitSet &/*conflictingAlts*/, atn::ATNConfigSet * /*configs*/) { +} + +void BaseErrorListener::reportContextSensitivity(Parser * /*recognizer*/, const dfa::DFA &/*dfa*/, size_t /*startIndex*/, + size_t /*stopIndex*/, size_t /*prediction*/, atn::ATNConfigSet * /*configs*/) { +} diff --git a/third_party/antlr4-runtime/BaseErrorListener.h b/third_party/antlr4-runtime/BaseErrorListener.h new file mode 100755 index 0000000..aad2e5d --- /dev/null +++ b/third_party/antlr4-runtime/BaseErrorListener.h @@ -0,0 +1,36 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "ANTLRErrorListener.h" + +namespace antlrcpp { + class BitSet; +} + +namespace antlr4 { + + /** + * Provides an empty default implementation of {@link ANTLRErrorListener}. The + * default implementation of each method does nothing, but can be overridden as + * necessary. + */ + class ANTLR4CPP_PUBLIC BaseErrorListener : public ANTLRErrorListener { + + virtual void syntaxError(Recognizer *recognizer, Token * offendingSymbol, size_t line, size_t charPositionInLine, + const std::string &msg, std::exception_ptr e) override; + + virtual void reportAmbiguity(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, bool exact, + const antlrcpp::BitSet &ambigAlts, atn::ATNConfigSet *configs) override; + + virtual void reportAttemptingFullContext(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, + const antlrcpp::BitSet &conflictingAlts, atn::ATNConfigSet *configs) override; + + virtual void reportContextSensitivity(Parser *recognizer, const dfa::DFA &dfa, size_t startIndex, size_t stopIndex, + size_t prediction, atn::ATNConfigSet *configs) override; + }; + +} // namespace antlr4 diff --git a/third_party/antlr4-runtime/BufferedTokenStream.cpp b/third_party/antlr4-runtime/BufferedTokenStream.cpp new file mode 100755 index 0000000..241dfe5 --- /dev/null +++ b/third_party/antlr4-runtime/BufferedTokenStream.cpp @@ -0,0 +1,414 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#include "WritableToken.h" +#include "Lexer.h" +#include "RuleContext.h" +#include "misc/Interval.h" +#include "Exceptions.h" +#include "support/CPPUtils.h" + +#include "BufferedTokenStream.h" + +using namespace antlr4; +using namespace antlrcpp; + +BufferedTokenStream::BufferedTokenStream(TokenSource *tokenSource) : _tokenSource(tokenSource){ + InitializeInstanceFields(); +} + +TokenSource* BufferedTokenStream::getTokenSource() const { + return _tokenSource; +} + +size_t BufferedTokenStream::index() { + return _p; +} + +ssize_t BufferedTokenStream::mark() { + return 0; +} + +void BufferedTokenStream::release(ssize_t /*marker*/) { + // no resources to release +} + +void BufferedTokenStream::reset() { + seek(0); +} + +void BufferedTokenStream::seek(size_t index) { + lazyInit(); + _p = adjustSeekIndex(index); +} + +size_t BufferedTokenStream::size() { + return _tokens.size(); +} + +void BufferedTokenStream::consume() { + bool skipEofCheck = false; + if (!_needSetup) { + if (_fetchedEOF) { + // the last token in tokens is EOF. skip check if p indexes any + // fetched token except the last. + skipEofCheck = _p < _tokens.size() - 1; + } else { + // no EOF token in tokens. skip check if p indexes a fetched token. + skipEofCheck = _p < _tokens.size(); + } + } else { + // not yet initialized + skipEofCheck = false; + } + + if (!skipEofCheck && LA(1) == Token::EOF) { + throw IllegalStateException("cannot consume EOF"); + } + + if (sync(_p + 1)) { + _p = adjustSeekIndex(_p + 1); + } +} + +bool BufferedTokenStream::sync(size_t i) { + if (i + 1 < _tokens.size()) + return true; + size_t n = i - _tokens.size() + 1; // how many more elements we need? + + if (n > 0) { + size_t fetched = fetch(n); + return fetched >= n; + } + + return true; +} + +size_t BufferedTokenStream::fetch(size_t n) { + if (_fetchedEOF) { + return 0; + } + + size_t i = 0; + while (i < n) { + std::unique_ptr t(_tokenSource->nextToken()); + + if (is(t.get())) { + (static_cast(t.get()))->setTokenIndex(_tokens.size()); + } + + _tokens.push_back(std::move(t)); + ++i; + + if (_tokens.back()->getType() == Token::EOF) { + _fetchedEOF = true; + break; + } + } + + return i; +} + +Token* BufferedTokenStream::get(size_t i) const { + if (i >= _tokens.size()) { + throw IndexOutOfBoundsException(std::string("token index ") + + std::to_string(i) + + std::string(" out of range 0..") + + std::to_string(_tokens.size() - 1)); + } + return _tokens[i].get(); +} + +std::vector BufferedTokenStream::get(size_t start, size_t stop) { + std::vector subset; + + lazyInit(); + + if (_tokens.empty()) { + return subset; + } + + if (stop >= _tokens.size()) { + stop = _tokens.size() - 1; + } + for (size_t i = start; i <= stop; i++) { + Token *t = _tokens[i].get(); + if (t->getType() == Token::EOF) { + break; + } + subset.push_back(t); + } + return subset; +} + +size_t BufferedTokenStream::LA(ssize_t i) { + return LT(i)->getType(); +} + +Token* BufferedTokenStream::LB(size_t k) { + if (k > _p) { + return nullptr; + } + return _tokens[_p - k].get(); +} + +Token* BufferedTokenStream::LT(ssize_t k) { + lazyInit(); + if (k == 0) { + return nullptr; + } + if (k < 0) { + return LB(-k); + } + + size_t i = _p + k - 1; + sync(i); + if (i >= _tokens.size()) { // return EOF token + // EOF must be last token + return _tokens.back().get(); + } + + return _tokens[i].get(); +} + +ssize_t BufferedTokenStream::adjustSeekIndex(size_t i) { + return i; +} + +void BufferedTokenStream::lazyInit() { + if (_needSetup) { + setup(); + } +} + +void BufferedTokenStream::setup() { + _needSetup = false; + sync(0); + _p = adjustSeekIndex(0); +} + +void BufferedTokenStream::setTokenSource(TokenSource *tokenSource) { + _tokenSource = tokenSource; + _tokens.clear(); + _fetchedEOF = false; + _needSetup = true; +} + +std::vector BufferedTokenStream::getTokens() { + std::vector result; + for (auto &t : _tokens) + result.push_back(t.get()); + return result; +} + +std::vector BufferedTokenStream::getTokens(size_t start, size_t stop) { + return getTokens(start, stop, std::vector()); +} + +std::vector BufferedTokenStream::getTokens(size_t start, size_t stop, const std::vector &types) { + lazyInit(); + if (stop >= _tokens.size() || start >= _tokens.size()) { + throw IndexOutOfBoundsException(std::string("start ") + + std::to_string(start) + + std::string(" or stop ") + + std::to_string(stop) + + std::string(" not in 0..") + + std::to_string(_tokens.size() - 1)); + } + + std::vector filteredTokens; + + if (start > stop) { + return filteredTokens; + } + + for (size_t i = start; i <= stop; i++) { + Token *tok = _tokens[i].get(); + + if (types.empty() || std::find(types.begin(), types.end(), tok->getType()) != types.end()) { + filteredTokens.push_back(tok); + } + } + return filteredTokens; +} + +std::vector BufferedTokenStream::getTokens(size_t start, size_t stop, size_t ttype) { + std::vector s; + s.push_back(ttype); + return getTokens(start, stop, s); +} + +ssize_t BufferedTokenStream::nextTokenOnChannel(size_t i, size_t channel) { + sync(i); + if (i >= size()) { + return size() - 1; + } + + Token *token = _tokens[i].get(); + while (token->getChannel() != channel) { + if (token->getType() == Token::EOF) { + return i; + } + i++; + sync(i); + token = _tokens[i].get(); + } + return i; +} + +ssize_t BufferedTokenStream::previousTokenOnChannel(size_t i, size_t channel) { + sync(i); + if (i >= size()) { + // the EOF token is on every channel + return size() - 1; + } + + while (true) { + Token *token = _tokens[i].get(); + if (token->getType() == Token::EOF || token->getChannel() == channel) { + return i; + } + + if (i == 0) + return -1; + i--; + } + return i; +} + +std::vector BufferedTokenStream::getHiddenTokensToRight(size_t tokenIndex, ssize_t channel) { + lazyInit(); + if (tokenIndex >= _tokens.size()) { + throw IndexOutOfBoundsException(std::to_string(tokenIndex) + " not in 0.." + std::to_string(_tokens.size() - 1)); + } + + ssize_t nextOnChannel = nextTokenOnChannel(tokenIndex + 1, Lexer::DEFAULT_TOKEN_CHANNEL); + size_t to; + size_t from = tokenIndex + 1; + // if none onchannel to right, nextOnChannel=-1 so set to = last token + if (nextOnChannel == -1) { + to = static_cast(size() - 1); + } else { + to = nextOnChannel; + } + + return filterForChannel(from, to, channel); +} + +std::vector BufferedTokenStream::getHiddenTokensToRight(size_t tokenIndex) { + return getHiddenTokensToRight(tokenIndex, -1); +} + +std::vector BufferedTokenStream::getHiddenTokensToLeft(size_t tokenIndex, ssize_t channel) { + lazyInit(); + if (tokenIndex >= _tokens.size()) { + throw IndexOutOfBoundsException(std::to_string(tokenIndex) + " not in 0.." + std::to_string(_tokens.size() - 1)); + } + + if (tokenIndex == 0) { + // Obviously no tokens can appear before the first token. + return { }; + } + + ssize_t prevOnChannel = previousTokenOnChannel(tokenIndex - 1, Lexer::DEFAULT_TOKEN_CHANNEL); + if (prevOnChannel == static_cast(tokenIndex - 1)) { + return { }; + } + // if none onchannel to left, prevOnChannel=-1 then from=0 + size_t from = static_cast(prevOnChannel + 1); + size_t to = tokenIndex - 1; + + return filterForChannel(from, to, channel); +} + +std::vector BufferedTokenStream::getHiddenTokensToLeft(size_t tokenIndex) { + return getHiddenTokensToLeft(tokenIndex, -1); +} + +std::vector BufferedTokenStream::filterForChannel(size_t from, size_t to, ssize_t channel) { + std::vector hidden; + for (size_t i = from; i <= to; i++) { + Token *t = _tokens[i].get(); + if (channel == -1) { + if (t->getChannel() != Lexer::DEFAULT_TOKEN_CHANNEL) { + hidden.push_back(t); + } + } else { + if (t->getChannel() == static_cast(channel)) { + hidden.push_back(t); + } + } + } + + return hidden; +} + +bool BufferedTokenStream::isInitialized() const { + return !_needSetup; +} + +/** + * Get the text of all tokens in this buffer. + */ +std::string BufferedTokenStream::getSourceName() const +{ + return _tokenSource->getSourceName(); +} + +std::string BufferedTokenStream::getText() { + fill(); + return getText(misc::Interval(0U, size() - 1)); +} + +std::string BufferedTokenStream::getText(const misc::Interval &interval) { + lazyInit(); + size_t start = interval.a; + size_t stop = interval.b; + if (start == INVALID_INDEX || stop == INVALID_INDEX) { + return ""; + } + sync(stop); + if (stop >= _tokens.size()) { + stop = _tokens.size() - 1; + } + + std::stringstream ss; + for (size_t i = start; i <= stop; i++) { + Token *t = _tokens[i].get(); + if (t->getType() == Token::EOF) { + break; + } + ss << t->getText(); + } + return ss.str(); +} + +std::string BufferedTokenStream::getText(RuleContext *ctx) { + return getText(ctx->getSourceInterval()); +} + +std::string BufferedTokenStream::getText(Token *start, Token *stop) { + if (start != nullptr && stop != nullptr) { + return getText(misc::Interval(start->getTokenIndex(), stop->getTokenIndex())); + } + + return ""; +} + +void BufferedTokenStream::fill() { + lazyInit(); + const size_t blockSize = 1000; + while (true) { + size_t fetched = fetch(blockSize); + if (fetched < blockSize) { + return; + } + } +} + +void BufferedTokenStream::InitializeInstanceFields() { + _needSetup = true; + _fetchedEOF = false; +} diff --git a/third_party/antlr4-runtime/BufferedTokenStream.h b/third_party/antlr4-runtime/BufferedTokenStream.h new file mode 100755 index 0000000..fab74d2 --- /dev/null +++ b/third_party/antlr4-runtime/BufferedTokenStream.h @@ -0,0 +1,200 @@ +/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. + * Use of this file is governed by the BSD 3-clause license that + * can be found in the LICENSE.txt file in the project root. + */ + +#pragma once + +#include "TokenStream.h" + +namespace antlr4 { + + /** + * This implementation of {@link TokenStream} loads tokens from a + * {@link TokenSource} on-demand, and places the tokens in a buffer to provide + * access to any previous token by index. + * + *

+ * This token stream ignores the value of {@link Token#getChannel}. If your + * parser requires the token stream filter tokens to only those on a particular + * channel, such as {@link Token#DEFAULT_CHANNEL} or + * {@link Token#HIDDEN_CHANNEL}, use a filtering token stream such a + * {@link CommonTokenStream}.

+ */ + class ANTLR4CPP_PUBLIC BufferedTokenStream : public TokenStream { + public: + BufferedTokenStream(TokenSource *tokenSource); + BufferedTokenStream(const BufferedTokenStream& other) = delete; + + BufferedTokenStream& operator = (const BufferedTokenStream& other) = delete; + + virtual TokenSource* getTokenSource() const override; + virtual size_t index() override; + virtual ssize_t mark() override; + + virtual void release(ssize_t marker) override; + virtual void reset(); + virtual void seek(size_t index) override; + + virtual size_t size() override; + virtual void consume() override; + + virtual Token* get(size_t i) const override; + + /// Get all tokens from start..stop inclusively. + virtual std::vector get(size_t start, size_t stop); + + virtual size_t LA(ssize_t i) override; + virtual Token* LT(ssize_t k) override; + + /// Reset this token stream by setting its token source. + virtual void setTokenSource(TokenSource *tokenSource); + virtual std::vector getTokens(); + virtual std::vector getTokens(size_t start, size_t stop); + + /// + /// Given a start and stop index, return a List of all tokens in + /// the token type BitSet. Return null if no tokens were found. This + /// method looks at both on and off channel tokens. + /// + virtual std::vector getTokens(size_t start, size_t stop, const std::vector &types); + virtual std::vector getTokens(size_t start, size_t stop, size_t ttype); + + /// Collect all tokens on specified channel to the right of + /// the current token up until we see a token on DEFAULT_TOKEN_CHANNEL or + /// EOF. If channel is -1, find any non default channel token. + virtual std::vector getHiddenTokensToRight(size_t tokenIndex, ssize_t channel); + + /// + /// Collect all hidden tokens (any off-default channel) to the right of + /// the current token up until we see a token on DEFAULT_TOKEN_CHANNEL + /// or EOF. + /// + virtual std::vector getHiddenTokensToRight(size_t tokenIndex); + + /// + /// Collect all tokens on specified channel to the left of + /// the current token up until we see a token on DEFAULT_TOKEN_CHANNEL. + /// If channel is -1, find any non default channel token. + /// + virtual std::vector getHiddenTokensToLeft(size_t tokenIndex, ssize_t channel); + + /// + /// Collect all hidden tokens (any off-default channel) to the left of + /// the current token up until we see a token on DEFAULT_TOKEN_CHANNEL. + /// + virtual std::vector getHiddenTokensToLeft(size_t tokenIndex); + + virtual std::string getSourceName() const override; + virtual std::string getText() override; + virtual std::string getText(const misc::Interval &interval) override; + virtual std::string getText(RuleContext *ctx) override; + virtual std::string getText(Token *start, Token *stop) override; + + /// Get all tokens from lexer until EOF. + virtual void fill(); + + protected: + /** + * The {@link TokenSource} from which tokens for this stream are fetched. + */ + TokenSource *_tokenSource; + + /** + * A collection of all tokens fetched from the token source. The list is + * considered a complete view of the input once {@link #fetchedEOF} is set + * to {@code true}. + */ + std::vector> _tokens; + + /** + * The index into {@link #tokens} of the current token (next token to + * {@link #consume}). {@link #tokens}{@code [}{@link #p}{@code ]} should be + * {@link #LT LT(1)}. + * + *

This field is set to -1 when the stream is first constructed or when + * {@link #setTokenSource} is called, indicating that the first token has + * not yet been fetched from the token source. For additional information, + * see the documentation of {@link IntStream} for a description of + * Initializing Methods.

+ */ + // ml: since -1 requires to make this member signed for just this single aspect we use a member _needSetup instead. + // Use bool isInitialized() to find out if this stream has started reading. + size_t _p; + + /** + * Indicates whether the {@link Token#EOF} token has been fetched from + * {@link #tokenSource} and added to {@link #tokens}. This field improves + * performance for the following cases: + * + *