Parsing Command Structure?

Expert (103)

28-12-2022, 22:21

I created a sort of DOS prompt because I am writing an adventure.

So I created a jump table that each function all you have to do is LD A with a number like 7 and it will jump to the 7th subroutine in that table. Pretty easy and strait forward.

However, I could not find any code out there that can parse a table with the commands such as GO, NORTH, UP, TREE or whatever and give it a number if you type it in.

I created a table with the commands of variable length and a buffer space to hold what you type in.

So I have the two things that I can compare such as...

LD HL, buffer
LD DE, Table

That was all I can figure out.
I suspect that it would be some routine to compare like...
LD A, (DE)
LD B, (HL)
Compare A and B

Then some routine after that to create a number between 0-255.

Is there source code or instruction to follow because I have looked through ZAK's, Assembly Language routines, MSX books and I can not find anything on the subject. I might even be working it wrong in my google search.

All help is welcome

!login ou Inscrivez-vous pour poster

Par aoineko

Paladin (1011)

28-12-2022, 23:41

If I understand correctly, you have an array of strings and you want to know the index of the string entered by the user (if it is there).

If that's right, the "brute force" way would be to compare the string to each of the entries in the array and return the index if the two strings are equal.
To compare two strings in z80 assembler, there is plenty of code on the internet.

For example:

;IN    HL     Address of string1.
;      DE     Address of string2.
;OUT   zero   Set if string1 = string2, reset if string1 != string2.
;      carry  Set if string1 > string2, reset if string1 <= string2.

CmpStrings:
    PUSH   HL
    PUSH   DE

    LD     A, (DE)          ; Compare lengths to determine smaller string
    CP     (HL)            ; (want to minimize work).
    JR     C, Str1IsBigger
    LD     A, (HL)

Str1IsBigger:
    LD     C, A             ; Put length in BC
    LD     B, 0
    INC    DE              ; Increment pointers to meat of string.
    INC    HL

CmpLoop:
    LD     A, (DE)          ; Compare bytes.
    CPI
    JR     NZ, NoMatch      ; If (HL) != (DE), abort.
    INC    DE              ; Update pointer.
    JP     PE, CmpLoop

    POP    DE
    POP    HL
    LD     A, (DE)          ; Check string lengths to see if really equal.
    CP     (HL)
    RET

NoMatch:
    DEC    HL
    CP     (HL)            ; Compare again to affect carry.
    POP    DE
    POP    HL
    RET

You should first convert the user's string to lower (or upper) case and have your table data with the same case for easy comparison.

Par Chilly Willy

Expert (103)

29-12-2022, 01:41

Well let me ask how would DOS or something like BASIC do it if it were Z80.

You have a table of commands like DW: DIR, RET, CD, EDIT and so on.

I could create a brute force method that checks just those words but that would get large if it were say 30 commands.

Surely BASIC has a command set that a word is matched which then goes through a jump table to the actual routine.

I would like to build a large vocabulary for this adventure game and just using GO NORTH or LOOK is boring.

The alternative is a bloated game unless I use a LUT of some type. Not to mention slower.

I wonder if there is a book on writing Z80 adventure games. If there is I have not been able to google it.

Either way I will try the CPI method and see how that works.
Thanks

Par Chilly Willy

Expert (103)

29-12-2022, 01:50

So if I understand how CPI can be incorporated would be something like.

HL = Buffer
DL = Table.

Take first byte of table like
Ld a, (de)
ld c, a
ld b, 0

So CPI will compare HL with the accumulator then increment to the next byte while decrementing BC

So the Table can be something like

DW: 3,DIR,255, 5,START,255, 3,BOB,255 4,POOP,255

probably be a good idea to add a 255 terminator on the end as well

I think I get it now.

Par thegeps

Paragon (1194)

29-12-2022, 02:58

Check this thread, you'll find the answer

NYYRIKKI taught me how to do it

https://www.msx.org/forum/msx-talk/development/secret-keyboa...

Par Chilly Willy

Expert (103)

29-12-2022, 03:25

thegeps wrote:

Check this thread, you'll find the answer

NYYRIKKI taught me how to do it

https://www.msx.org/forum/msx-talk/development/secret-keyboard-sequence

Great concept but it uses BIOS routines which makes this impossible to port to another system.
I love to write universal code and I know there is a formula but these things are usually in house talk between coders in the glory days of the 80's.

I love when people write pure code that is not dependent on the magic of some poorly written BIOS just to get the product out the door.

Par aoineko

Paladin (1011)

29-12-2022, 09:39

I don't know how BASIC and DOS parse their commands (surely someone has the answer), but if I had to do it myself and performance was important, I would go for a dichotomous search and/or a hash table.

- For the first one, you just have to sort your commands in alphabetical order, test the middle of the table and find out not only if the user's string matches a command, but if not, if it is smaller or bigger than the command. Depending on the result you start the process again on the upper or lower part of your table, again and again.

- For the 2nd, you have to find a way to hash your commands to obtain a number that will be used to arrange them in sub-arrays. It depends on the number of commands, but a hash of 16, 32 or 64 entries would probably be sufficient for a game. A naïve approach would be to use for example the first letter of the command as a hash key (a bit like in the old telephone directories) but it doesn't work well if many commands start with the same letter. Personally, I will use a simple solution that works well: accumulate the value of all the letters. As you will have to go through the user's string to know its length, it is almost free to accumulate all the letters in a register and use this value as a hash key.

If you have a really large number of possible commands (say several hundred), combining the two techniques could be cost effective.

EDIT: By the way, the NYYRIKKI code uses only the BIOS to acquire the user string. The rest of the code is BIOS-free, so it is very easy to adapt it to your needs.

Par santiontanon

Paragon (1810)

29-12-2022, 12:02

This all depends on how flexible you want your parser to be:
- If you just want a flat list of commands (e.g., each string like "go north" is a command), then the fastest way is using what aoineko mentions: implement a prefix tree or a hash table to map your commands to functions (you don't even need to translate commands to integers, just map commands to functions directly, and then call the function).
- If you want a more flexible grammar, where commands have a verb, arguments, etc. then the standard way is to define a grammar. This is usually done in a several steps (any book on "compilers" will have chapters and chapters dedicated to this). The first step is the "tokenizer", that splits the input sentence into tokens, for example: "go north" will be divided into ["go", "north"], the next step is the "grammar parser", that reads one token at a time and identifies verbs, arguments, etc. (or whatever terminal/non-terminal symbols does your grammar have). The parse is usually stored as a "parse tree", which is then given to a third step, the "semantic analyzer", that does whatever it needs to do (call a function with the proper arguments in case of a DOS interpreter, translate code to the target language in case of a compiler, etc.). For a simple parser in a text adventure, you probably do not need a full-blown grammar, and just a simple "verb + list of arguments" grammar (that can be hardcoded) is enough).

I know I did not provide many details, but hopefully the keywords I used help you in searching for code examples.

If you are looking for books, this is my recommendation:
- If you want to just go directly to practical things on the Z80/BASIC, check out the classic books by Tim Hartnell, he wrote lots of books about these topics. For example this one or this one.
- If you want to learn about command parsers (or natural language parsers) in general, I recommend you check a compilers book. The standard classic university text book that most of us learned from is this one.

Par thegeps

Paragon (1194)

29-12-2022, 12:19

Chilly Willy wrote:

thegeps wrote:

Check this thread, you'll find the answer

NYYRIKKI taught me how to do it

https://www.msx.org/forum/msx-talk/development/secret-keyboard-sequence

I love when people write pure code that is not dependent on the magic of some poorly written BIOS just to get the product out the door.

Well it uses bios routine only to get input from the keyboard. You can find (and copy in your code) those routines from the msx bios listing (easily available in pdf on web, google is your friend). Keyboard is connected through ports to Z80, and I think each Z80 machine has its own way to interact with its keyboard, so you can't have a universal Z80 code except the one to check the parser (so all that code except the bios routines)
And last (but not least): MSX bios isn't a "poorly written" one. Taking a look at it is enough to prove the nonsense you just spit out

Par Chilly Willy

Expert (103)

30-12-2022, 21:28

aoineko wrote:

If I understand correctly, you have an array of strings and you want to know the index of the string entered by the user (if it is there).

For example:

;IN    HL     Address of string1.
;      DE     Address of string2.
;OUT   zero   Set if string1 = string2, reset if string1 != string2.
;      carry  Set if string1 > string2, reset if string1 <= string2.

CmpStrings:
    PUSH   HL
    PUSH   DE

    LD     A, (DE)          ; Compare lengths to determine smaller string
    CP     (HL)            ; (want to minimize work).
    JR     C, Str1IsBigger
    LD     A, (HL)

Str1IsBigger:
    LD     C, A             ; Put length in BC
    LD     B, 0
    INC    DE              ; Increment pointers to meat of string.
    INC    HL

CmpLoop:
    LD     A, (DE)          ; Compare bytes.
    CPI
    JR     NZ, NoMatch      ; If (HL) != (DE), abort.
    INC    DE              ; Update pointer.
    JP     PE, CmpLoop

    POP    DE
    POP    HL
    LD     A, (DE)          ; Check string lengths to see if really equal.
    CP     (HL)
    RET

NoMatch:
    DEC    HL
    CP     (HL)            ; Compare again to affect carry.
    POP    DE
    POP    HL
    RET

You should first convert the user's string to lower (or upper) case and have your table data with the same case for easy comparison.

I used a scaled down form of this, thank you so much for your help.

Thank everyone for that matter.

Par NYYRIKKI

Enlighted (6067)

31-12-2022, 14:55

Chilly Willy wrote:

thegeps wrote:

Check this thread, you'll find the answer

NYYRIKKI taught me how to do it

https://www.msx.org/forum/msx-talk/development/secret-keyboard-sequence

I love when people write pure code that is not dependent on the magic of some poorly written BIOS just to get the product out the door.

Well... This was not a direct reply to your question, but for another very similar and therefore it had "outer layer" to fill the buffer. If you would have just deleted that very first routine, you would have found the answer that you were looking for. My tip to you is that patience is a good skill to learn for any coder.