User:Softtest123/USRP
This is the beginning of long overdue documentation for the Useful Self Replicating Program, (USRP).
USRP is a compiler compiler compiler, a program capable of generating compiler compilers. It is based upon a self descriptive language. That language is an attributed grammar. The language, JBN, is an extension of a slightly modified version of Extended Backus–Naur form (EBNF). JBN is capable of describing itself with attributes such that when processed by USRP produces USRP. Other languages can be described in JBN and by processing with USRP will produce processors of those languages.
The current operating version of USRP generates C language programs. A self port to Java is being considered.
One useful application has been to construct MODEL, a program that processes JBN to produce programs that generate strings in the defined language, a useful idea for generating test cases and large quantities of data.
JBN: The Language
[edit]The important differences between JBN and EBNF is in the identification of rule names, the addition of attributes, and the use of metacharacters
Rule Names
[edit]Rule names are surrounded by greater than and less than signs: <Rule Name>. This allows literals to be expressed "literally". Literals may also be formed within single or double quote marks and are treated exactly as expressed, where literals expressed without quotes and containing only letters will be considered as key words such that 'if' will not match 'ifthen'. (Herein, single quotes are delimiters only and should be ignored.)
Rules
[edit]Rules are stated normally:
<Rule Name> ::= 'Expression to be matched'
Language Elements
Language elements include literals, options, Kleene stars, and semantic rules.
- Literals take two forms, unquoted and quoted. When quoted an exact match of the quoted contents is required. Quoted literals may contain spaces and other special characters such as the C language new line (\n) and tab (\t) characters. Unquoted strings may not contain spaces but may contain JBN meta-characters.
- Options are surrounded by square brackets ([]) and may contain one of Rule Name, or Literal and zero or more semantic rules. Options must match zero or one times.
- Kleene Stars are surrounded by braces ({}) and may contain one of Rule Name, or Literal and zero or more semantic rules. Kleene Stars must match zero or more times.
- Semantic Rules are surrounded by parentheses '()' and contain one or more valid statements in the target language, e.g., C.
- Meta Characters require and escape character to form literals. That escape character is '/' and is, itself, a meta character. For instance to match a '/' it must be preceded by '/' as '//'
- Rule A rule name is used within a rule to invoke another rule (or itself recursively). Rule names must consist of valid identifier characters of the target language and spaces (that are deleted when code is generated).
- Required Elements A required element is a literal or a rule. The first required element of a rule, when not present in the input stream, will cause the rule to be rejected. The second and successive required elements will cause an error to be generated when the first required element is matched but a successive required element fails to match.
- Choice Alternative rules under a Rule Name are distinguished by a vertical bar, '|'
Example Rule
[edit]<This Rule> ::= Literal {" "} [// (printf("/ Not found;\n"/);)] <This Rule> | Alternative Rule (printf("Not a keyword match.\n"/);) | AlternativeRule Mismatches | AlternativeRuleMatches
USRP will generate code from this statement that will parse
Literal AlternativeRuleMatches
USRP will generate the code:
/* This program generated by usrp Rev. 1.11, 2007 by Alan A. Jorgensen */ char * ProgID[]={"This program generated by usrp Rev. 1.11, 2007 by Alan A. Jorgensen"}; int ThisRule() { if (KeyMatches("Literal")) { while (Matches(" ")); if (Matches("/")) { ; printf(" Not found;\n"); } if (!ThisRule()) error("ThisRule"); return TRUE; } if (KeyMatches("Alternative")) { if (!KeyMatches("Rule")) error("Rule"); printf("Not a keyword match.\n"); return TRUE; } if (KeyMatches("AlternativeRule")) { if (!KeyMatches("Mismatches")) error("Mismatches"); return TRUE; } if (KeyMatches("AlternativeRuleMatches")) { return TRUE; } return FALSE; }