Method and apparatus for program development using a grammar-sensitive editor

• US 6,016,467 A
• Filed: 05/27/1997
• Issued: 01/18/2000
• Est. Priority Date: 05/27/1997
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Newsted, Gary Michael, Ryen, Richard Eugene
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/863,653
• Time in Patent Office: 966 Days
• Field of Search: 704/8, 704/9, 395/708, 707/530, 707/531, 707/533, 434/156, 434/167
• US Class Current: 704/9
• CPC Class Codes: G06F 8/33 Intelligent editors
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Techniques used in program development using a grammar sensitive editor are described. Input within an edit buffer is processed by a lexical and syntax analyzer in response to various syntactic and lexical states. Actions such as updating various multimedia indices are performed. Users are guided through program development through prompts for menu selection. The items transmitted on the menu are in accordance with the current state of lexical and syntactic processing. If an input in the edit buffer is invalid, the erroneous text is detected via the lexical and syntax analyzers and the erroneous text is highlighted. Additionally, transmitted via the menu is a selection of correct and valid alternatives from which the user may select to be included in the edit buffer.

Claims

1. A method of performing grammar sensitive editing of user input represented by one or more tokens, said method comprising the steps of:

detecting a trigger event;

performing, in response to detection of said trigger event, lexical and syntactical analysis of said user input;

transmitting, responsive to detection of an erroneous token by said performing step, one or more valid language options for use in place of said erroneous token; and

transmitting, responsive to detection of no erroneous tokens by said performing step, one or more subsequent language options;

wherein the step of transmitting one or more language options and the step of transmitting one or more subsequent language options include transmitting a menu of one or more symbols based upon grammar rules defining syntax rules of input language, said menu including one or more first right hand side symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.

2. The method of claim 1 further including the step of:

monitoring said user input for an input selection of a transmitted language option.

3. The method of claim 1 further including the step of:

updating, in response to said performing step, a media index by invoking an action routine.

4. The method of claim 3, wherein said media index is associated with a help file used to transmit help information to a user upon detection of said erroneous token, and the method further including the step of:

marking said erroneous token in said user input upon detection of said erroneous token.

5. The method of claim 3, wherein said media index is associated with a multimedia device which operates in response to said performing step.

6. The method of claim 5 further including the step of:

operating said multimedia device in response to said performing step wherein said multimedia device has a corresponding multimedia data type describing a type of data associated with the multimedia device, said multimedia data type being one of the following;

an image data type in which one or more images are transmitted responsive to said performing step, and a physical action data type in which one or more physical actions are taken by a mechanical device responsive to said performing step.

7. The method of claim 3 further including the step of:

playing, in response to said performing step, a recorded sound associated with said media index.

8. The method of claim 7, wherein said recorded sound is one of the following:

instructions used upon detection of said erroneous token, a message played in response to detecting no erroneous tokens, a first language recording played in response to user input of a second language.

9. The method of claim 1 further including the step of invoking, upon detection of said erroneous token, a fault handler to perform error processing, said error processing including the following steps:

determining if said erroneous token is a template-insert token, said template-insert token being a predefined sequence of one or more characters used to indicate that user-specific input is required; and

upon determining that said erroneous token is said template-insert token, removing said template-insert token from said user input.

10. The method of claim 9 further including the step of:

transmitting template data responsive to determining that said erroneous token is said template-insert token.

11. The method of claim 9, wherein said fault handler restores an analysis state to a previous state, said analysis state being associated with said step of performing lexical and syntactical analysis in accordance with said grammar rules, said analysis state corresponding to one of said grammar rules and a symbol included in said one grammar rule representing a state in a finite state machine used in said performing step in lexical and syntactical analysis, said previous state being associated with a symbol included in said user input which said performing step has determined to be a valid token of said input language.

12. The method of claim 11, wherein said syntactical analysis of said performing step includes the step of:

transitioning between states of said finite state machine in response to said user input in accordance with predefined grammar rules in a grammar rule table representing syntax of an input language, each of said predefined grammar rules including a left-hand side nonterminal symbol associated with one or more right-hand side symbols, each of said states being associated with one of said predefined grammar rules and a right-hand side symbol, and said language options transmitted in response to detecting an erroneous token correspond to one or more valid states subsequent to said previous state of said finite state machine, said one or more valid states representing replacement selections for said erroneous token.

13. The method of claim 1, wherein said syntactical analysis of said performing step includes transitioning between states of a finite state machine in response to said user input in accordance with predefined grammar rules in a grammar rule table representing syntax of an input language, each of said predefined grammar rules including a left-hand side nonterminal symbol associated with one or more right-hand side symbols, each of said states being associated with one of said predefined grammar rules and a right-hand side symbol, and wherein said step of transmitting one or more valid language options upon detection of an erroneous token, and said step of transmitting one or more subsequent language options in response to detecting no erroneous tokens further include the steps of:

retrieving grammar rule table indices from a cross-reference table using a state number as an index into said cross-reference table, said state number corresponding to one of said states;

retrieving a nonterminal symbol from said grammar rule table using said grammar rule table indices, said nonterminal symbol being a right-hand side symbol;

using said nonterminal symbol as a left-hand side symbol to retrieve from said grammar rule table any first occurring right-hand side symbols associated with grammar rules for which said nonterminal symbol is included as a left-hand side symbol; and

transmitting said nonterminal symbol and said first occurring right-hand side symbols.

14. The method of claim 13 wherein, said steps of transmitting said one or more subsequent language options upon detection of no erroneous tokens, and transmitting one or more valid language options upon detection of an erroneous token further include the following steps when one of said language options transmitted is a nonterminal symbol having a null symbol as one of said first occurring right-hand side symbols, the method including the steps of:

providing an indicator denoting that said left-hand side nonterminal symbol is optional; and

retrieving from an empty-goto table a subsequent recovery state corresponding to the next state to which processing resumes if said left-hand side nonterminal symbol is omitted.

15. The method of claim 14, wherein said step of providing an indicator includes the step of replacing the null symbol with a character sequence of one or more characters which are transmitted indicating that said left-hand side nonterminal symbol is optional.

16. The method of claim 14, wherein one of said language options transmitted is selected, and the method further includes the steps of:

determining if said one language option selected corresponds to said nonterminal symbol having a null symbol as a first occurring right-hand side symbol indicating that said nonterminal symbol is optional; and

upon determining that said one language option selected is optional, performing the following steps;

restoring a current processing state to be said subsequent recovery state causing said performing step to resume lexical and syntactical processing.

17. The method of claim 1, wherein said syntactical analysis of said performing step includes transitioning between states of a finite state machine in response to said user input in accordance with predefined grammar rules in a grammar rule table representing syntax of an input language, each of said predefined grammar rules including a left-hand side nonterminal symbol associated with one or more right-hand side symbols, each of said states being associated with one of said predefined grammar rules and a right-hand side symbol, and the method further includes the steps of:

detecting a selection of a language option transmitted;

determining, in response to said detecting step, if said language option corresponds to a nonterminal symbol or a terminal symbol in which nonterminal symbols and terminal symbols appear in the right-hand side of grammar rules defining a syntax associated with said input language;

if said language option corresponds to a terminal symbol, performing the following steps;

including said terminal symbol into an edit buffer associated with said user input;

determining a next state of said finite state machine;

determining if said next state corresponds to a terminal symbol or a nonterminal symbol;

if said next state corresponds to a terminal symbol, including said terminal symbol and a trigger character in with said user input to trigger said performing step; and

if said next state corresponds to a nonterminal symbol, expanding said nonterminal symbol in accordance with said grammar rules by determining which grammar rules have said nonterminal symbol as a left-hand side nonterminal symbol; and

if said language option corresponds to a nonterminal symbol, performing the following step;

expanding said nonterminal symbol in accordance with said grammar rules by determining which of said grammar rules have said nonterminal symbol as a left-hand side nonterminal symbol.

18. The method of claim 1, wherein said syntactical analysis of said performing step includes transitioning between states of a finite state machine in response to said user input in accordance with predefined grammar rules in a grammar rule table representing syntax of an input language, each of said predefined grammar rules including a left-hand side nonterminal symbol associated with one or more right-hand side symbols, each of said states being associated with one of said predefined grammar rules and a right-hand side symbol, and in response to said performing step detecting no erroneous tokens, the method further includes the steps of:

determining a next state of said finite state machine;

determining if said next state corresponds to a terminal symbol or a nonterminal symbol;

upon determining that said next state corresponds to a terminal symbol, performing the following steps;

transmitting type information about said terminal symbol; and

accepting additional input associated with said terminal symbol in accordance with said type information.

19. The method according to claim 18, wherein said step of transmitting type information includes the steps of:

determining a type of said terminal symbol;

upon determining that said terminal symbol is one of an integer or string, prompting the user for a specific value that is included in an edit buffer associated with said user input;

upon determining that said terminal symbol is a variable name, prompting the user for a specific value for said variable name; and

upon determining that said terminal symbol corresponds to an optional argument, restoring a current processing state to be a previously saved subsequent optional state allowing said performing step to resume lexical and syntactical analysis.

20. The method of claim 1, wherein said input language is a programming language, said user input includes source code statements of said programming language.

21. The method of claim 1, wherein said lexical analysis of said performing step is performed using a lexical analyzer and said syntactical analysis of said performing step is performed using a syntax analyzer, said lexical analyzer being produced by a lexical analyzer generator, said syntax analyzer being produced by a syntax analyzer generator, said syntax analyzer generator producing an empty-goto table, and cross reference table, said empty-goto table defining a recovery state subsequent to an optional state corresponding to an optional language element, said recovery state indicating a state of which syntactical analysis resumes when an optional language element is skipped, and said cross reference table identifying, for a given state of a finite state machine used in said performing step, state information used to obtain a symbol denoting a language option corresponding to said state.

22. The method of claim 21 wherein said syntax analyzer generator produces a grammar rule table and a token name table, said grammar rule table including grammar rules defining syntax of said input language, each of said grammar rules including a left-hand side symbol and one or more corresponding right-hand side symbols, said left-hand side symbol being a nonterminal symbol, said right-hand side symbols including terminal and nonterminal symbols, nonterminal symbols being expandable in terms of other grammar rules included in said grammar rule table, said token name table being used to distinguish nonterminal symbols from terminal symbols included in said grammar rule table.

23. The method of claim 22, wherein an input set of syntax rules are input to said syntax analyzer generator defining syntax of said input language, said input set being in a form interpreted by said syntax analyzer generator, one or more action routines being specified in said set of syntax rules, a first action routine being associated with a first syntax rule of said set of syntax rules, said first action routine corresponding to code that is executed when processing said first syntax rule.

24. The method of claim 23, wherein said first action routine is used in preparing an income tax form.

25. The method of claim 23 further including the step of:

transmitting, responsive to detection of no erroneous tokens by said performing step, one or more subsequent language options.

26. The method of claim 1, wherein said step of detecting a trigger event in said user input includes the step of detecting a predetermined trigger character in said user input.

27. The method of claim 1, wherein said step of detecting a trigger event in said user input includes the step of selecting a menu item.

28. The method of claim 1, wherein said step of detecting a trigger event in said user input includes the step of detecting a verbal command.

29. The method of claim 1, wherein said lexical and syntactical analysis of said performing step is performed upon user input up to a specified cursor position or to the end of a file in accordance with a preselected analysis mode.

30. The method of claim 22, wherein said first action routine is used in preparing form-based input.

31. A memory for storing instructions executable by a computer, the memory comprising:

detector means for detecting a trigger event;

analysis means, coupled to said detector means, for performing lexical and syntactical analysis of user input represented by one or more tokens;

erroneous token detector means, coupled to said analysis means, for detecting an erroneous token in said user input, said erroneous token detector means transmitting one or more valid language options for use in place of said erroneous token; and

means, coupled to said analysis means, for transmitting one or more subsequent language options if said analysis means detects only valid tokens;

wherein said erroneous token detector means and said means for transmitting include means for transmitting a menu of one or more symbols based upon grammar rules defining syntax rules of input language said menu including one or more first right hand side symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.

32. A computer system comprising:

user interface means for interfacing with a user to transmit input and output;

analysis means, coupled to said user interface means, for performing lexical and syntax analysis of user input;

error transmitter means, coupled to said analyzer means, for transmitting one or more options to said user interface means when said analysis means detects no errors in said user input, said one or more options representing one or more subsequent input options; and

means for transmitting a menu of one or more symbols based upon grammar rules defining syntax rules of input language, said menu including one or more first right hand symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.

33. The computer system of claim 32, wherein said user interface means includes an editor and a system device.

34. An apparatus comprising:

an option selector for selecting an option from a transmitted menu of one or more options;

a menu processor, coupled to said option selector, which receives and processes said option selected with said option selector;

a lexical and syntax analyzer, coupled to said menu processor, which performs lexical and syntax analysis upon user input;

an error transmitter, coupled to said lexical and syntax analyzer, for transmitting said one or more options included in said transmitted menu when said lexical and syntax analyzer detects an error in said user input, said one or more options representing one or more valid options for use in correcting said error; and

a transmitter, coupled to said lexical and syntax analyzer, for transmitting one or more options included in said transmitted menu when said lexical and syntax analyzer detects no errors in said user input, said one or more options representing one or more subsequent input options;

said transmitted menu including one or more symbols based upon grammar rules defining syntax rules of input language, said menu including one or more first right hand symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.

35. The apparatus of claim 34 further comprising:

an editor, coupled to said lexical and syntax analyzer, which transmits user input for processing to said lexical and syntax analyzer.

36. A method of performing grammar sensitive editing of user input represented by one or more tokens, said method comprising the steps of:

detecting a trigger event;

performing, in response to detection of said trigger event, lexical and syntactical analysis of user input; and

transmitting, responsive to detection of no erroneous tokens by said performing step, one or more subsequent language options;

wherein the transmitting step includes transmitting a menu of one or more symbols based upon grammar rules defining syntax rules of input language, said menu including one or more first right hand side symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.

37. The method of claim 36 further including the step of:

transmitting, responsive to detection of an erroneous token by said performing step, one or more valid language options for use in place of said erroneous token.

38. A method of performing grammar sensitive editing of user input represented by one or more tokens, said method comprising the steps of:

detecting a trigger event;

performing, in response to detection of said trigger event, lexical and syntactical analysis of said user input; and

transmitting, responsive to detection of an erroneous token by said performing step, one or more valid language options for use in place of said erroneous token;

wherein the step of transmitting includes transmitting one or more symbols based upon grammar rules defining syntax rules of input language, said menu including one or more first right hand side symbols corresponding to an expanded non-terminal symbol in accordance with said grammar rules defining syntax rules of said input language.