lexer.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "bytes"
  12. "encoding/json"
  13. "fmt"
  14. "regexp"
  15. "strconv"
  16. "strings"
  17. "unicode"
  18. "unicode/utf8"
  19. )
  20. var namePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  21. var numberPattern = regexp.MustCompile("^[0-9].*$")
  22. /*
  23. LexToken represents a token which is returned by the lexer.
  24. */
  25. type LexToken struct {
  26. ID LexTokenID // Token kind
  27. Pos int // Starting position (in bytes)
  28. Val string // Token value
  29. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  30. Lline int // Line in the input this token appears
  31. Lpos int // Position in the input line this token appears
  32. }
  33. /*
  34. NewLexTokenInstance creates a new LexToken object instance from given LexToken values.
  35. */
  36. func NewLexTokenInstance(t LexToken) *LexToken {
  37. return &LexToken{
  38. t.ID,
  39. t.Pos,
  40. t.Val,
  41. t.Identifier,
  42. t.Lline,
  43. t.Lpos,
  44. }
  45. }
  46. /*
  47. Equal checks if this LexToken equals another LexToken. Returns also a message describing
  48. what is the found difference.
  49. */
  50. func (n LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  51. var res = true
  52. var msg = ""
  53. if n.ID != other.ID {
  54. res = false
  55. msg += fmt.Sprintf("ID is different %v vs %v\n", n.ID, other.ID)
  56. }
  57. if !ignorePosition && n.Pos != other.Pos {
  58. res = false
  59. msg += fmt.Sprintf("Pos is different %v vs %v\n", n.Pos, other.Pos)
  60. }
  61. if n.Val != other.Val {
  62. res = false
  63. msg += fmt.Sprintf("Val is different %v vs %v\n", n.Val, other.Val)
  64. }
  65. if n.Identifier != other.Identifier {
  66. res = false
  67. msg += fmt.Sprintf("Identifier is different %v vs %v\n", n.Identifier, other.Identifier)
  68. }
  69. if !ignorePosition && n.Lline != other.Lline {
  70. res = false
  71. msg += fmt.Sprintf("Lline is different %v vs %v\n", n.Lline, other.Lline)
  72. }
  73. if !ignorePosition && n.Lpos != other.Lpos {
  74. res = false
  75. msg += fmt.Sprintf("Lpos is different %v vs %v\n", n.Lpos, other.Lpos)
  76. }
  77. if msg != "" {
  78. var buf bytes.Buffer
  79. out, _ := json.MarshalIndent(n, "", " ")
  80. buf.WriteString(string(out))
  81. buf.WriteString("\nvs\n")
  82. out, _ = json.MarshalIndent(other, "", " ")
  83. buf.WriteString(string(out))
  84. msg = fmt.Sprintf("%v%v", msg, buf.String())
  85. }
  86. return res, msg
  87. }
  88. /*
  89. PosString returns the position of this token in the origianl input as a string.
  90. */
  91. func (t LexToken) PosString() string {
  92. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  93. }
  94. /*
  95. String returns a string representation of a token.
  96. */
  97. func (t LexToken) String() string {
  98. prefix := ""
  99. if !t.Identifier {
  100. prefix = "v:" // Value is not an identifier
  101. }
  102. switch {
  103. case t.ID == TokenEOF:
  104. return "EOF"
  105. case t.ID == TokenError:
  106. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  107. case t.ID == TokenPRECOMMENT:
  108. return fmt.Sprintf("/* %s */", t.Val)
  109. case t.ID == TokenPOSTCOMMENT:
  110. return fmt.Sprintf("# %s", t.Val)
  111. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  112. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  113. case t.ID > TOKENodeKEYWORDS:
  114. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  115. case len(t.Val) > 20:
  116. // Special case for very long values
  117. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  118. }
  119. return fmt.Sprintf("%s%q", prefix, t.Val)
  120. }
  121. // Meta data interface
  122. /*
  123. Type returns the meta data type.
  124. */
  125. func (t LexToken) Type() string {
  126. if t.ID == TokenPRECOMMENT {
  127. return MetaDataPreComment
  128. } else if t.ID == TokenPOSTCOMMENT {
  129. return MetaDataPostComment
  130. }
  131. return MetaDataGeneral
  132. }
  133. /*
  134. Value returns the meta data value.
  135. */
  136. func (t LexToken) Value() string {
  137. return t.Val
  138. }
  139. /*
  140. KeywordMap is a map of keywords - these require spaces between them
  141. */
  142. var KeywordMap = map[string]LexTokenID{
  143. // Import statement
  144. "import": TokenIMPORT,
  145. "as": TokenAS,
  146. // Sink definition
  147. "sink": TokenSINK,
  148. "kindmatch": TokenKINDMATCH,
  149. "scopematch": TokenSCOPEMATCH,
  150. "statematch": TokenSTATEMATCH,
  151. "priority": TokenPRIORITY,
  152. "suppresses": TokenSUPPRESSES,
  153. // Function definition
  154. "func": TokenFUNC,
  155. "return": TokenRETURN,
  156. // Boolean operators
  157. "and": TokenAND,
  158. "or": TokenOR,
  159. "not": TokenNOT,
  160. // String operators
  161. "like": TokenLIKE,
  162. "hasprefix": TokenHASPREFIX,
  163. "hassuffix": TokenHASSUFFIX,
  164. // List operators
  165. "in": TokenIN,
  166. "notin": TokenNOTIN,
  167. // Constant terminals
  168. "false": TokenFALSE,
  169. "true": TokenTRUE,
  170. "null": TokenNULL,
  171. // Conditional statements
  172. "if": TokenIF,
  173. "elif": TokenELIF,
  174. "else": TokenELSE,
  175. // Loop statements
  176. "for": TokenFOR,
  177. "break": TokenBREAK,
  178. "continue": TokenCONTINUE,
  179. }
  180. /*
  181. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  182. Symbols can be maximal 2 characters long.
  183. */
  184. var SymbolMap = map[string]LexTokenID{
  185. // Condition operators
  186. ">=": TokenGEQ,
  187. "<=": TokenLEQ,
  188. "!=": TokenNEQ,
  189. "==": TokenEQ,
  190. ">": TokenGT,
  191. "<": TokenLT,
  192. // Grouping symbols
  193. "(": TokenLPAREN,
  194. ")": TokenRPAREN,
  195. "[": TokenLBRACK,
  196. "]": TokenRBRACK,
  197. "{": TokenLBRACE,
  198. "}": TokenRBRACE,
  199. // Separators
  200. ".": TokenDOT,
  201. ",": TokenCOMMA,
  202. ";": TokenSEMICOLON,
  203. // Grouping
  204. ":": TokenCOLON,
  205. "=": TokenEQUAL,
  206. // Arithmetic operators
  207. "+": TokenPLUS,
  208. "-": TokenMINUS,
  209. "*": TokenTIMES,
  210. "/": TokenDIV,
  211. "//": TokenDIVINT,
  212. "%": TokenMODINT,
  213. // Assignment statement
  214. ":=": TokenASSIGN,
  215. }
  216. // Lexer
  217. // =====
  218. /*
  219. RuneEOF is a special rune which represents the end of the input
  220. */
  221. const RuneEOF = -1
  222. /*
  223. Function which represents the current state of the lexer and returns the next state
  224. */
  225. type lexFunc func(*lexer) lexFunc
  226. /*
  227. Lexer data structure
  228. */
  229. type lexer struct {
  230. name string // Name to identify the input
  231. input string // Input string of the lexer
  232. pos int // Current rune pointer
  233. line int // Current line pointer
  234. lastnl int // Last newline position
  235. width int // Width of last rune
  236. start int // Start position of the current red token
  237. tokens chan LexToken // Channel for lexer output
  238. }
  239. /*
  240. Lex lexes a given input. Returns a channel which contains tokens.
  241. */
  242. func Lex(name string, input string) chan LexToken {
  243. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  244. go l.run()
  245. return l.tokens
  246. }
  247. /*
  248. LexToList lexes a given input. Returns a list of tokens.
  249. */
  250. func LexToList(name string, input string) []LexToken {
  251. var tokens []LexToken
  252. for t := range Lex(name, input) {
  253. tokens = append(tokens, t)
  254. }
  255. return tokens
  256. }
  257. /*
  258. Main loop of the lexer.
  259. */
  260. func (l *lexer) run() {
  261. if skipWhiteSpace(l) {
  262. for state := lexToken; state != nil; {
  263. state = state(l)
  264. if !skipWhiteSpace(l) {
  265. break
  266. }
  267. }
  268. }
  269. close(l.tokens)
  270. }
  271. /*
  272. next returns the next rune in the input and advances the current rune pointer
  273. if peek is 0. If peek is >0 then the nth character is returned without advancing
  274. the rune pointer.
  275. */
  276. func (l *lexer) next(peek int) rune {
  277. // Check if we reached the end
  278. if int(l.pos) >= len(l.input) {
  279. return RuneEOF
  280. }
  281. // Decode the next rune
  282. pos := l.pos
  283. if peek > 0 {
  284. pos += peek - 1
  285. }
  286. r, w := utf8.DecodeRuneInString(l.input[pos:])
  287. if peek == 0 {
  288. l.width = w
  289. l.pos += l.width
  290. }
  291. return r
  292. }
  293. /*
  294. backup sets the pointer one rune back. Can only be called once per next call.
  295. */
  296. func (l *lexer) backup(width int) {
  297. if width == 0 {
  298. width = l.width
  299. }
  300. l.pos -= width
  301. }
  302. /*
  303. startNew starts a new token.
  304. */
  305. func (l *lexer) startNew() {
  306. l.start = l.pos
  307. }
  308. /*
  309. emitToken passes a token back to the client.
  310. */
  311. func (l *lexer) emitToken(t LexTokenID) {
  312. if t == TokenEOF {
  313. l.emitTokenAndValue(t, "", false)
  314. return
  315. }
  316. if l.tokens != nil {
  317. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false,
  318. l.line + 1, l.start - l.lastnl + 1}
  319. }
  320. }
  321. /*
  322. emitTokenAndValue passes a token with a given value back to the client.
  323. */
  324. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool) {
  325. if l.tokens != nil {
  326. l.tokens <- LexToken{t, l.start, val, identifier, l.line + 1, l.start - l.lastnl + 1}
  327. }
  328. }
  329. /*
  330. emitError passes an error token back to the client.
  331. */
  332. func (l *lexer) emitError(msg string) {
  333. if l.tokens != nil {
  334. l.tokens <- LexToken{TokenError, l.start, msg, false, l.line + 1, l.start - l.lastnl + 1}
  335. }
  336. }
  337. // Helper functions
  338. // ================
  339. /*
  340. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  341. reaches EOF while skipping whitespaces.
  342. */
  343. func skipWhiteSpace(l *lexer) bool {
  344. r := l.next(0)
  345. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  346. if r == '\n' {
  347. l.line++
  348. l.lastnl = l.pos
  349. }
  350. r = l.next(0)
  351. if r == RuneEOF {
  352. l.emitToken(TokenEOF)
  353. return false
  354. }
  355. }
  356. l.backup(0)
  357. return true
  358. }
  359. /*
  360. lexTextBlock lexes a block of text without whitespaces. Interprets
  361. optionally all one or two letter tokens.
  362. */
  363. func lexTextBlock(l *lexer, interpretToken bool) {
  364. r := l.next(0)
  365. if interpretToken {
  366. // Check if we start with a known symbol
  367. nr := l.next(1)
  368. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  369. l.next(0)
  370. return
  371. }
  372. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  373. return
  374. }
  375. }
  376. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  377. if interpretToken {
  378. // Check if we find a token in the block
  379. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  380. l.backup(0)
  381. return
  382. }
  383. nr := l.next(1)
  384. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  385. l.backup(0)
  386. return
  387. }
  388. }
  389. r = l.next(0)
  390. }
  391. if r != RuneEOF {
  392. l.backup(0)
  393. }
  394. }
  395. /*
  396. lexNumberBlock lexes a block potentially containing a number.
  397. */
  398. func lexNumberBlock(l *lexer) {
  399. r := l.next(0)
  400. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  401. if !unicode.IsNumber(r) && r != '.' {
  402. if r == 'e' {
  403. l1 := l.next(1)
  404. l2 := l.next(2)
  405. if l1 != '+' || !unicode.IsNumber(l2) {
  406. break
  407. }
  408. l.next(0)
  409. l.next(0)
  410. } else {
  411. break
  412. }
  413. }
  414. r = l.next(0)
  415. }
  416. if r != RuneEOF {
  417. l.backup(0)
  418. }
  419. }
  420. // State functions
  421. // ===============
  422. /*
  423. lexToken is the main entry function for the lexer.
  424. */
  425. func lexToken(l *lexer) lexFunc {
  426. // Check if we got a quoted value or a comment
  427. n1 := l.next(1)
  428. n2 := l.next(2)
  429. // Parse comments
  430. if (n1 == '/' && n2 == '*') || n1 == '#' {
  431. return lexComment
  432. }
  433. // Parse strings
  434. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  435. return lexValue
  436. }
  437. // Lex a block of text and emit any found tokens
  438. l.startNew()
  439. // First try to parse a number
  440. lexNumberBlock(l)
  441. identifierCandidate := l.input[l.start:l.pos]
  442. keywordCandidate := strings.ToLower(identifierCandidate)
  443. // Check for number
  444. if numberPattern.MatchString(keywordCandidate) {
  445. _, err := strconv.ParseFloat(keywordCandidate, 64)
  446. if err == nil {
  447. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false)
  448. return lexToken
  449. }
  450. }
  451. if len(keywordCandidate) > 0 {
  452. l.backup(l.pos - l.start)
  453. }
  454. lexTextBlock(l, true)
  455. identifierCandidate = l.input[l.start:l.pos]
  456. keywordCandidate = strings.ToLower(identifierCandidate)
  457. // Check for keyword
  458. token, ok := KeywordMap[keywordCandidate]
  459. if !ok {
  460. // Check for symbol
  461. token, ok = SymbolMap[keywordCandidate]
  462. }
  463. if ok {
  464. // A known token was found
  465. l.emitToken(token)
  466. } else {
  467. if !namePattern.MatchString(keywordCandidate) {
  468. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  469. return nil
  470. }
  471. // An identifier was found
  472. l.emitTokenAndValue(TokenIDENTIFIER, identifierCandidate, true)
  473. }
  474. return lexToken
  475. }
  476. /*
  477. lexValue lexes a string value.
  478. Values can be declared in different ways:
  479. ' ... ' or " ... "
  480. Characters are parsed between quotes (escape sequences are interpreted)
  481. r' ... ' or r" ... "
  482. Characters are parsed plain between quote
  483. */
  484. func lexValue(l *lexer) lexFunc {
  485. var endToken rune
  486. l.startNew()
  487. allowEscapes := false
  488. r := l.next(0)
  489. // Check if we have a raw quoted string
  490. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  491. endToken = q
  492. l.next(0)
  493. } else {
  494. allowEscapes = true
  495. endToken = r
  496. }
  497. r = l.next(0)
  498. rprev := ' '
  499. lLine := l.line
  500. lLastnl := l.lastnl
  501. for (!allowEscapes && r != endToken) ||
  502. (allowEscapes && (r != endToken || rprev == '\\')) {
  503. if r == '\n' {
  504. lLine++
  505. lLastnl = l.pos
  506. }
  507. rprev = r
  508. r = l.next(0)
  509. if r == RuneEOF {
  510. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  511. return nil
  512. }
  513. }
  514. if allowEscapes {
  515. val := l.input[l.start+1 : l.pos-1]
  516. // Interpret escape sequences right away
  517. if endToken == '\'' {
  518. // Escape double quotes in a single quoted string
  519. val = strings.Replace(val, "\"", "\\\"", -1)
  520. }
  521. s, err := strconv.Unquote("\"" + val + "\"")
  522. if err != nil {
  523. l.emitError(err.Error() + " while parsing string")
  524. return nil
  525. }
  526. l.emitTokenAndValue(TokenSTRING, s, true)
  527. } else {
  528. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], true)
  529. }
  530. // Set newline
  531. l.line = lLine
  532. l.lastnl = lLastnl
  533. return lexToken
  534. }
  535. /*
  536. lexComment lexes comments.
  537. */
  538. func lexComment(l *lexer) lexFunc {
  539. // Consume initial /*
  540. r := l.next(0)
  541. if r == '#' {
  542. l.startNew()
  543. for r != '\n' && r != RuneEOF {
  544. r = l.next(0)
  545. }
  546. l.emitTokenAndValue(TokenPOSTCOMMENT, l.input[l.start:l.pos], false)
  547. if r == RuneEOF {
  548. return nil
  549. }
  550. l.line++
  551. } else {
  552. l.next(0)
  553. lLine := l.line
  554. lLastnl := l.lastnl
  555. l.startNew()
  556. r = l.next(0)
  557. for r != '*' && l.next(1) != '/' {
  558. if r == '\n' {
  559. lLine++
  560. lLastnl = l.pos
  561. }
  562. r = l.next(0)
  563. if r == RuneEOF {
  564. l.emitError("Unexpected end while reading comment")
  565. return nil
  566. }
  567. }
  568. l.emitTokenAndValue(TokenPRECOMMENT, l.input[l.start:l.pos-1], false)
  569. // Consume final /
  570. l.next(0)
  571. // Set newline
  572. l.line = lLine
  573. l.lastnl = lLastnl
  574. }
  575. return lexToken
  576. }