+ Reply to Thread
Results 1 to 15 of 15
  1. #1
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,264

    Default String matching?

    I'm playing around with the idea of writing a SCPI-parser. I need to match an incomming string to a series (could be dozens or hundreds) commands/keywords. For example an incoming string might look like OUTP:CH1 ON or MEAS:CURRC? so I need to create a list of all the keywords and then try to figure out which (if any) matches what's in the incomming string.

    My idea is to use the db directive to store the keywords as null-terminated strings, like so:
    Code:
    ASM
    Keywords
       db "OUTP", 0
       db "MEAS", 0
       db "CURR", 0
       db "VOLT", 0
       db "AC", 0
       db "DC", 0
       db "ON", 0
       db "OFF", 0
    ENDASM
    Obviously way simplified but it serves as an example.

    I can use the EXT modifier to "get" the address in FLASH where the table Keywords starts and then use READCODE to get a char at the time and match against my incomming string. But as soon as a char doesn't match I'd rather not continue to the NULL of that keyword but instead jump to the start of the next keyword.

    For that I think I'll need another table holding the addresses of where EACH keyword starts but I can't seem to figure out a way to build that table "automatically". I suppose I could do it at runtime and use WRITECODE to store it back into FLASH on the very first time the code executes but ideally I'd like the assembler (or pre-processor) to create that table for me and put it somewhere in FLASH where I can read it with READCODE.

    Does that make sense? Any ideas of how to achieve this? Or, for that matter any ideas in general on how to perform string matching would be welcome!

    /Henrik.

  2. #2

    Default Re: String matching?

    How about just storing the length of the string as part of the table?
    Code:
    ASM
    Keywords
       db 5, "OUTP", 0
       db 5, "MEAS", 0
       db 5, "CURR", 0
       db 5, "VOLT", 0
       db 3, "AC", 0
       db 3, "DC", 0
       db 3, "ON", 0
       db 4, "OFF", 0
       db 0		; end of table
    ENDASM

  3. #3
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,264

    Default Re: String matching?

    Thanks! I've thought about that and it might be how it'll end up but it's quite prone to errors so I would like a more automatic way - if one existed. An upside of that idea is, I think, that it won't need a NULL-terminator.

    /Henrik.

  4. #4
    Join Date
    Sep 2009
    Posts
    776

    Default Re: String matching?

    Maybe make Keyword label? And check each?
    But reading flash is fast, so I think simple loop can do that really fast.
    Eg:
    Code:
    If (char<>cmdChar) then gosub ReadToEnd
    ReadToEnd:
    READCODE Addr,TmpB
    IF TmpB<>0 THEN
     Addr=Addr+1
     GOTO ReadToEnd
    ENDIF
    RETURN
    This should be really fast if command are short as you mention.
    There is no magic way to know where one strings end, and another starts. You can use labels for each, write location as suggested, or loop to end.

  5. #5
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,264

    Default Re: String matching?

    Thanks!
    I can't imagine having a label for EACH keyword (if that's what you mean) and even if I do that I don't know of a way that lets me index thru them. Unless I somehow can construct an array of EXT variables/constants which would then contain the address of each keyword label - in flash. Or perhaps I'm missing something.

    Perhaps the "just read'n'skip to null" as you've shown is the best way. I might have to run some benchmark tests on that and see how fast it'll run thru a couple of hundred keywords.

    /Henrik.

  6. #6
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    i would be inclined to -
    make a fixed length array for all the key words, sort the elements into ascii order
    its much easier and faster to seek matches that way
    This is more entertaining than Free to Air TV

  7. #7
    Join Date
    Sep 2009
    Posts
    776

    Default Re: String matching?

    That would be fastest option, and you can jump to specific letter when starting. But there are some wasted FLASH...
    Henrik, why speed is so important?
    I used arrayread for parsing simple commands...
    Darrel posted somewhere example of that...

  8. #8
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    with a bit of asm and a pic18 you can set the tablepointer to keywords
    Code:
        movlw   UPPER Keywords
        movwf   TBLPTRU
        movlw   HIGH Keywords
        movwf   TBLPTRH
        movlw   LOW Keywords
        movwf   TBLPTRL
    and cycle through the flash with this ,it loads flash to wreg and post incs tablepointer to next byte
    Code:
     tblrd   *+
       movf   TABLAT,w
    its about 1000 times faster than readcode
    This is more entertaining than Free to Air TV

  9. #9
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,264

    Default Re: String matching?

    Thanks guys!
    I suppose everything is relative but I always try my best to write efficient code both from speed, size and readability point of view. I don't have any particular number I need to hit here in terms of speed but speed, in this case, is important because a command string might consist of 3-5 keywords to be matched out of a list of a, say, a hundred building up a complete command. Traversing thru every keyword in the list even if it's a mismatch on the first letter (and doing that for each keyword in the string) just "feels" wrong and not very efficient but in the end it might just BE the most efficient compromise between speed and size anyway.

    I've not used ARRAYREAD much but its modifiers are like for HSERIN so if I'm not mistaken you need to specify what you're looking for but if you have hundreds of combinations of keywords I'm not sure how that'll pan out. And if ARRAYREAD is anything like ARRAYWRITE (which takes 6 (IIRC) bytes per character) it's not really what I'd call efficient from a code size point of view.

    At this point my main interest was if someone knew of way to automatically generate a table with addresses but I suppose that's not the case. Using a fixed length is indeed another option as it would easily let me index the table of keywords. It comes at the cost of some wasted flash but it might be worth it.

    Richard, thank you! These kinds of snippets are very helpful! Once in W do I need to copy it out of there in order to compare it against my "input char" or can I compare my "input char" directly against "the content of W" (using PBP)?

    I'm gonna have to find some time to sit down and have a play with this.

    /Henrik.
    Last edited by HenrikOlsson; - 1st October 2019 at 17:13.

  10. #10
    Join Date
    Apr 2014
    Location
    Northeast
    Posts
    312

    Default Re: String matching?

    You could create a SELECT CASE where you CASE: in alphabetical order. For multiple key words starting with the same letter, use IF/THEN clauses to sort through them. SELECT CASE will parse through the first letter (in ascending order) until it finds the first letter. If you only have one selection that starts with that letter, you don't even need to work through the rest of the command/key word.
    I don't need the world to know my name, but I want to live a life so all my great-grandchildren proudly remember me.

  11. #11
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    Once in W do I need to copy it out of there in order to compare it against my "input char" or can I compare my "input char" directly against "the content of W" (using PBP)?
    there are numerous strategies possible
    if you had a byte var say chr2test , you can write wreg to that byte that a pbp macro
    MOVE?AB _chr2test
    and then perform your tests

    or subtract the char to test from wreg and look for a zero result for a match

    i think there are compare macro's in pbp that could be employed too. i have not used them

    once you find a keyword match whats next ? would a two dimensional array be more appropriate ?
    This is more entertaining than Free to Air TV

  12. #12
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    compare macro fwiw

    CMPEQ?BBL macro Bin1, Bin2, Label
    CLRWDT?
    MOVE?BA Bin1
    CHK?RP Bin2
    subwf Bin2, W
    BIT?GOTO 1, STATUS, Z, Label
    endm
    This is more entertaining than Free to Air TV

  13. #13
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    just as a comparison , this is so easy to accomplish in C

    the forum seems to be broken , can't upload any pics of the printout


    Code:
    #include <xc.h>
    
    #include "ks0108.h"
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include <stdint.h>
    
    
    const char* keyWords[][5] = {
        {"OUTP"},
        {"MEAS"},
        {"CURR"},
        {"VOLT"},
        {"AC"},
        {"DC"},
        {"ON"},
        {"OFF"}};
    
    
    int seekKey(char * buff) {
        int x;
        for (x = 0; x< sizeof keyWords / sizeof keyWords[0]; x++) {
            if (!strcmp(buff, *keyWords[x]))
                return x;
        }
        return -1; //fail
    }
    
    
    void main(void) {
        uint8_t contrast = 235;
        char buff[32];
        char instr[] = "OUTP:CH1 ON,MEAS:CURR AC";
        char * sep_tok = ",: ";
        char * p;
        int index;
        TRISA = 0B11111111;
        TRISB = 0B01110001;
        TRISC = 0B11111000;
        TRISE = 0B00000101;
        CMCON = 7;
        ADCON1 = 7;
        gE_LAT = 0;
        T2CON = 4;
        PR2 = 255;
        CCP1CON = 12;
        CCPR1L = contrast;
    
    
        GlcdInit();
    
    
    
    
        GlcdCls();
        p = strtok(instr, sep_tok);
        char ln = 0;
        while (p) {
            index = seekKey(p);
            GlcdStr(1, ln * 8, p);
            if (index < 0)
                GlcdStr(30, ln * 8, "fail");
            else {
                sprintf(buff, "keyword match %d", index);
                GlcdStr(30, ln * 8, buff);
            }
            ln++;
            gUpdate();
            p = strtok(NULL, sep_tok);
        }
    
    
    
    
    
    
        while (1) {
            __delay_ms(100);
        }
    }
    Last edited by richard; - 2nd October 2019 at 14:31.
    This is more entertaining than Free to Air TV

  14. #14

    Default Re: String matching?

    or you can pick a location in flash to store starting place with the "org" directive


    Capture.JPG

  15. #15
    Join Date
    May 2013
    Location
    australia
    Posts
    1,729

    Default Re: String matching?

    i might have got a picture of the printout to load



    henrik.jpg
    This is more entertaining than Free to Air TV

Similar Threads

  1. Matching time conditions
    By malc-c in forum mel PIC BASIC Pro
    Replies: 48
    Last Post: - 13th April 2010, 20:22
  2. Replies: 1
    Last Post: - 28th January 2010, 22:15
  3. Pulse count matching
    By RodSTAR in forum mel PIC BASIC Pro
    Replies: 5
    Last Post: - 22nd April 2008, 03:35
  4. Need help with matching
    By Christopher4187 in forum mel PIC BASIC Pro
    Replies: 2
    Last Post: - 28th January 2007, 13:45
  5. Image Matching Modules
    By sayzer in forum Off Topic
    Replies: 0
    Last Post: - 4th March 2006, 11:59

Members who have read this thread : 21

You do not have permission to view the list of names.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts